Two-Way Counter Machines and Diophantine Equations

DOI10.1145/322326.322340MaRDI QIDQ3960829zbMATH OpenOpenAlexFDO

Authors Eitan M. Gurari, Oscar H. Ibarra

Publication date 1982

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/322326.322340

zbMATH Keywords

Diophantine polynomialsemptiness problemHilbert's tenth problemnumber-theoretic problems

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Turing machines and related notions (03D10) Decidability (number-theoretic aspects) (11U05)

Cited in

(15)

• Variations on the technique of Ďuriš and Galil
• A note on Parikh maps, abstract languages, and decision problems
• Fooling a two way automaton or one pushdown store is better than one counter for two way machines
• Reachability analysis of reversal-bounded automata on series-parallel graphs
• On two-way nondeterministic finite automata with one reversal-bounded counter
• Quantum versus deterministic counter automata
• A technique for proving decidability of containment and equivalence of linear constraint queries
• On two-way FA with monotonic counters and quadratic Diophantine equations
• Finding numerical solutions of Diophantine equations using ant colony optimization
• Interference automata
• ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS
• GENERALIZED COUNTERS AND REVERSAL COMPLEXITY
• Two-way counter machines and finite-state transducers†
• New decidability results concerning two-way counter machines and applications
• Reachability analysis of reversal-bounded automata on series-parallel graphs

This page was built for publication: Two-Way Counter Machines and Diophantine Equations

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