Variations of checking stack automata: obtaining unexpected decidability properties

DOI10.1016/j.tcs.2018.04.024zbMath1395.68170arXiv1705.09732OpenAlexW2618109676MaRDI QIDQ5915651

Ian McQuillan, Oscar H. Ibarra

Publication date: 18 June 2018

Published in: Theoretical Computer Science, Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1705.09732

zbMATH Keywords

decidabilitypushdown automatareversal-bounded counterschecking stack automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines ⋮ On the complexity of decision problems for some classes of machines and applications ⋮ Tree-walking-storage automata ⋮ Generalizations of Checking Stack Automata: Characterizations and Hierarchies ⋮ On families of full trios containing counter machine languages ⋮ Semilinearity of Families of Languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reversal-bounded multipushdown machines
• The power of two-way deterministic checking stack automata
• Some decision problems concerning semilinearity and commutation.
• Checking automata and one-way stack languages
• Two-Way Counter Machines and Diophantine Equations
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• New Decidability Results Concerning Two-Way Counter Machines

This page was built for publication: Variations of checking stack automata: obtaining unexpected decidability properties