On decision problems for parameterized machines

DOI10.1016/j.tcs.2009.12.013zbMath1186.68259OpenAlexW2071293683MaRDI QIDQ2268878

Hsu-Chun Yen, Oscar H. Ibarra, Igor Potapov

Publication date: 9 March 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.12.013

zbMATH Keywords

Turing machinesdecision problemspushdown automatacounter machinesparameterized machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The equivalence problem of multitape finite automata
• Complete formal systems for equivalence problems
• ON STATELESS TWO-PUSHDOWN AUTOMATA AND RESTARTING AUTOMATA
• ON STATELESS AUTOMATA AND P SYSTEMS
• On Stateless Multihead Automata: Hierarchies and the Emptiness Problem