ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS

DOI10.1142/S0129054108006042MaRDI QIDQ3526543zbMATH OpenFDO

Authors Oscar H. Ibarra, Zhe Dang, Linmin Yang

Publication date 25 September 2008

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

Full work available at URL https://doi.org/10.1142/S0129054108006042

zbMATH Keywords

reversal-bounded counterstransition systems

Mathematics Subject Classification ID

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

Recommendations

• Diophantine equations, Presburger arithmetic and finite automata
• scientific article; zbMATH DE number 1759429
• scientific article; zbMATH DE number 4191113
• scientific article; zbMATH DE number 3648797
• Boundedness problems for Minsky counter machines
• Boundedness problems for Minsky counter machines
• Unboundedness problems for machines with reversal-bounded counters
• Notes on counting with finite machines
• Register machine proof of the theorem on exponential diophantine representation of enumerable sets
• On fixpoint arithmetic and infinite time Turing machines

Cites work

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

Cited in

(7)

• Counter machines and verification problems.
• On two-way FA with monotonic counters and quadratic Diophantine equations
• On the termination problem for counter machines with incrementing errors
• New complexity results for some linear counting problems using minimal solutions to linear Diophantine equations (extended abstract)
• Linear reachability problems and minimal solutions to linear Diophantine equation systems
• Store languages of Turing machines and counter machines
• On the solvability of a class of Diophantine equations and applications

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3526543)