Language recognition by two-way deterministic pushdown automata

DOI10.1007/S10559-005-0034-7zbMath1101.68661OpenAlexW1987397434MaRDI QIDQ2571535

D. A. Koval', L. P. Lisovik

Publication date: 11 November 2005

Published in: Cybernetics and Systems Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10559-005-0034-7

zbMATH Keywords

context-free languagesemilinear setautomaton with a finite-rotary counter

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Deterministic two-way one-head pushdown automata are very powerful
• A hardest language recognized by two-way nondeterministic pushdown automata
• Fooling a two way automaton or one pushdown store is better than one counter for two way machines
• A characterization of semilinear sets
• Solvable problems for transformers with reversal-bounded counters
• Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
• Unnamed Item

This page was built for publication: Language recognition by two-way deterministic pushdown automata