Word-mappings of level 2

A sequence of natural numbers is said to have {\em level k}, for some natural integer $k$, if it can be computed by a deterministic pushdown automaton of level $k$ ([Fratani-Sénizergues, APAL, 2006]). We show here that the sequences of level 2 are exactly the rational formal power series over one un...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2013-08, Vol.54, p.111-148
Main Authors: Ferté, Julien, Marin, Nathalie Nathalie, Sénizergues, Géraud
Format: Article
Language:English
Subjects:
Computer Science
Formal Languages and Automata Theory
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A sequence of natural numbers is said to have {\em level k}, for some natural integer $k$, if it can be computed by a deterministic pushdown automaton of level $k$ ([Fratani-Sénizergues, APAL, 2006]). We show here that the sequences of level 2 are exactly the rational formal power series over one undeterminate. More generally, we study mappings {\em from words to words} and show that the following classes coincide:\\ - the mappings which are computable by deterministic pushdown automata of level $2$\\ - the mappings which are solution of a system of catenative recurrence equations\\ - the mappings which are definable as a Lindenmayer system of type HDT0L.\\ We illustrate the usefulness of this characterization by proving three statements about formal power series, rational sets of homomorphisms and equations in words.
ISSN:1432-4350
1433-0490