Word-Mappings of Level 2

作者：Ferte Julien; Marin Nathalie; Senizergues Geraud^*

来源：Theory of Computing Systems, 2014, 54(1): 111-148.

DOI：10.1007/s00224-013-9489-5

• Iterated pushdown automata
• L-systems
• Integer sequences
• Rational power series
• Word sequences
• Word equations

A sequence of natural numbers is said to have level k, for some natural integer k, if it can be computed by a deterministic pushdown automaton of level k (Fratani and Senizergues in Ann Pure Appl. Log. 141:363-411, 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 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.

• 出版日期2014-1