Hierarchy theorems for two-way finite state transducers

DOI10.1007/BF00264603zbMath0398.68038OpenAlexW2026530784MaRDI QIDQ1254110

Sheila A. Greibach

Publication date: 1978

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00264603

zbMATH Keywords

Etol LanguagesHierarchy ResultsIndexed LanguagesSemiabstract Family of LanguagesTwo-Way Finite State Transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Representations of language families by homomorphic equality operations and generalized equality sets, Iterated stack automata and complexity classes, The failure of the strong pumping lemma for multiple context-free languages, Ogden's lemma, multiple context-free grammars, and the control language hierarchy, Finite transducers and rational transductions, Three hierarchies of transducers, Hierarchies of hyper-AFLs, Output string languages of compositions of deterministic macro tree transducers