Two-Way Counter Machines and Diophantine Equations
From MaRDI portal
Publication:3960829
DOI10.1145/322326.322340zbMath0496.03020OpenAlexW1974451646MaRDI QIDQ3960829
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
Decidability (number-theoretic aspects) (11U05) Decidability of theories and sets of sentences (03B25) Turing machines and related notions (03D10)
Related Items
On two-way FA with monotonic counters and quadratic Diophantine equations, Unnamed Item, ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS, Fooling a two way automaton or one pushdown store is better than one counter for two way machines, New decidability results concerning two-way counter machines and applications, 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, Variations of checking stack automata: obtaining unexpected decidability properties, GENERALIZED COUNTERS AND REVERSAL COMPLEXITY, Finding numerical solutions of Diophantine equations using ant colony optimization, Interference automata, A technique for proving decidability of containment and equivalence of linear constraint queries, Two-way counter machines and finite-state transducers†, Variations on the technique of Ďuriš and Galil, A note on Parikh maps, abstract languages, and decision problems
