Hierarchy theorems for two-way finite state transducers

DOI10.1007/BF00264603MaRDI QIDQ1254110zbMATH OpenOpenAlexFDO

Authors 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)

Cited in

(8)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1254110)