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

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

This page was built for publication: A characterization of two-way deterministic classes of languages