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

• Published in: Theoretical computer science 2004-01, Vol.312 (2), p.359-378
• Main Authors: Ibarra, Oscar H., Dang, Zhe
• Format: Article
• Language: English
• Subjects: Applied sciences; Computer science; control theory; systems; Decidability; Exact sciences and technology; Miscellaneous; Monotonic counter; Presburger relation; Quadratic Diophantine equation; Reachability problem; Semilinear set; Theoretical computing; Two-way finite automaton
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2003.10.027

We show an interesting connection between two-way deterministic finite automata with monotonic counters and quadratic Diophantine equations. The automaton M operates on inputs of the form a 1 i 1 ⋯ a n i n for some fixed n and distinct symbols a 1,…, a n , where i 1,…, i n are nonnegative integers. We consider the following reachability problem: given a machine M, a state q, and a Presburger relation E over counter values, is there ( i 1,…, i n ) such that M, when started in its initial state on the left end of the input a 1 i 1 ⋯ a n i n with all counters initially zero, reaches some configuration where the state is q and the counter values satisfy E? In particular, we look at the case when the relation E is an equality relation, i.e., a conjunction of relations of the form C i = C j . We show that this case and variations of it are equivalent to the solvability of some special classes of systems of quadratic Diophantine equations. We also study the nondeterministic version of two-way finite automata augmented with monotonic counters with respect to the reachability problem. Finally, we introduce a technique which uses decidability and undecidability results to show “separation” between language classes.