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

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

Oscar H. Ibarra, Zhe Dang

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

DecidabilitySemilinear setMonotonic counterPresburger relationReachability problem Quadratic Diophantine equationTwo-way finite automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quadratic and bilinear Diophantine equations (11D09) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Automata sequences (11B85)

Related Items (4)

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item

This page was built for publication: On two-way FA with monotonic counters and quadratic Diophantine equations