Iterated sequential transducers as language generating devices

DOI10.1016/j.tcs.2006.07.059zbMath1142.68420OpenAlexW2073589167MaRDI QIDQ861252

Henning Bordihn, Markus Holzer, Carlos Martín-Vide, Henning Fernau, Vincenzo Manca

Publication date: 9 January 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.07.059

zbMATH Keywords

Lindenmayer systemsstate complexityfinite state sequential transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items

Iterated uniform finite-state transducers on unary languages ⋮ Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers* ⋮ A computation model with automatic functions and relations as primitive operations ⋮ Alternating automatic register machines ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Iterated uniform finite-state transducers on unary languages ⋮ Descriptional complexity of iterated uniform finite-state transducers ⋮ Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power

Cites Work

• Iterated GSMs and CO-CFL
• Programmed OL-systems
• Information transmission in il systems^∗
• Automata Studies. (AM-34)
• Normal forms for phrase-structure grammars
• Description of developmental languages using recurrence systems
• The maximum invariant set of an automaton system
• Iterated a-NGSM maps and Γ systems
• Closure under union and composition of iterated rational transductions
• ON THE GENERATIVE POWER OF ITERATED TRANSDUCTION
• A note on some systems of lindenmayer
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item