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 (8)

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

This page was built for publication: Hierarchy theorems for two-way finite state transducers