On two-way FA with monotonic counters and quadratic Diophantine equations

DOI10.1016/j.tcs.2003.10.027zbMath1084.68062MaRDI QIDQ1884954

Zhe Dang, Oscar H. Ibarra

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2003.10.027

zbMATH Keywords

Decidability; Semilinear set; Monotonic counter; Presburger relation; Reachability problem Quadratic Diophantine equation; Two-way finite automaton

Mathematics Subject Classification ID

68Q45: Formal languages and automata

11D09: Quadratic and bilinear Diophantine equations

03D05: Automata and formal grammars in connection with logical questions

03B25: Decidability of theories and sets of sentences

11B85: Automata sequences

Related Items

On the solvability of a class of Diophantine equations and applications, On two-way nondeterministic finite automata with one reversal-bounded counter, Reachability in Succinct and Parametric One-Counter Automata, ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS

Cites Work

• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The complexity of decision problems for finite-turn multicounter machines
• Semigroups, Presburger formulas, and languages
• Two-Way Counter Machines and Diophantine Equations
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• The Diophantine Problem for Addition and Divisibility
• New Decidability Results Concerning Two-Way Counter Machines