On the complexity of decision problems for some classes of machines and applications

DOI10.1016/j.ic.2023.105080MaRDI QIDQ6077841

Ian McQuillan, Oscar H. Ibarra

Publication date: 27 September 2023

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

computational complexitycoding theorycounter machinesreversal-bounded countersdecidableundecidable

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The effect of end-markers on counter machines and commutativity
• On the containment and equivalence problems for two-way transducers
• Descriptional and computational complexity of finite automata -- a survey
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Pushdown automata with reversal-bounded counters
• The complexity of decision problems for finite-turn multicounter machines
• Reversal-bounded multipushdown machines
• Complete problems for deterministic polynomial time
• Generalizations of Code Languages with Marginal Errors
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• On the Tape Complexity of Deterministic Context-Free Languages
• New Decidability Results Concerning Two-Way Counter Machines
• State-complexity of finite-state devices, state compressibility and incompressibility
• Mathematical Foundations of Computer Science 2005
• Deterministic context free languages
• Stack automata and compiling
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Variations of checking stack automata: obtaining unexpected decidability properties
• Generalizations of Code Languages with Marginal Errors

This page was built for publication: On the complexity of decision problems for some classes of machines and applications