Journal article
On two-way FA with monotonic counters and quadratic Diophantine equations
Theoretical computer science, Vol.312(2), pp.359-378
2004
Handle:
https://hdl.handle.net/2376/106079
Abstract
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.
Metrics
7 Record Views
Details
- Title
- On two-way FA with monotonic counters and quadratic Diophantine equations
- Creators
- Oscar H Ibarra - Department of Computer Science, University of California, Santa Barbara, CA 93106, USAZhe Dang - School of Electrical Engineering and Computer Science, Washington State University, Pullman, WA 99164, USA
- Publication Details
- Theoretical computer science, Vol.312(2), pp.359-378
- Academic Unit
- Electrical Engineering and Computer Science, School of
- Publisher
- Elsevier B.V
- Identifiers
- 99900546678701842
- Language
- English
- Resource Type
- Journal article