A characterization of two-way deterministic classes of languages

DOI10.1016/S0022-0000(70)80027-7zbMath0222.68034OpenAlexW2001907947MaRDI QIDQ2547802

A. V. Aho, Jeffrey D. Ullman

Publication date: 1970

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(70)80027-7

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index, Characterizations of transductions defined by abstract families of transducers, Tree transducers, L systems, and two-way machines, Unnamed Item, Two-way A-transducers and AFL, Classes of formal grammars, The power of two-way deterministic checking stack automata, Absolutely parallel grammars and two-way finite-state transducers, Three hierarchies of transducers, Hierarchies of hyper-AFLs

Cites Work

• Unnamed Item
• Abstract families of processors
• Abstract families of deterministic languages
• An Approach to a Unified Theory of Automata
• Two-way pushdown automata
• Studies in abstract families of languages
• Two-way balloon automata and AFL