ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS

DOI10.1142/S0129054108006042zbMath1164.68013MaRDI QIDQ3526543

Oscar H. Ibarra, Linmin Yang, Zhe Dang

Publication date: 25 September 2008

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

transition systemsreversal-bounded counters

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability (number-theoretic aspects) (11U05) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60) Decidability of theories and sets of sentences (03B25)

Cites Work

• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• On the solvability of a class of Diophantine equations and applications
• The complexity of decision problems for finite-turn multicounter machines
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• A theory of timed automata
• On two-way FA with monotonic counters and quadratic Diophantine equations
• Decidability of model checking for infinite-state concurrent systems
• Semigroups, Presburger formulas, and languages
• Two-Way Counter Machines and Diophantine Equations
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• New Decidability Results Concerning Two-Way Counter Machines
• Unnamed Item

This page was built for publication: ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS