We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Word-Mappings of Level 2.
- Authors
Ferté, Julien; Marin, Nathalie; Sénizergues, Géraud
- Abstract
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 Sénizergues in Ann Pure Appl. Log. 141:363-411, ). 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: We illustrate the usefulness of this characterization by proving three statements about formal power series, rational sets of homomorphisms and equations in words.
- Subjects
NATURAL numbers; MATHEMATICAL sequences; POWER series; MATHEMATICAL mappings; SET theory; HOMOMORPHISMS
- Publication
Theory of Computing Systems, 2014, Vol 54, Issue 1, p111
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-013-9489-5