Journal article
On two-way nondeterministic finite automata with one reversal-bounded counter
Theoretical computer science, Vol.330(1), pp.59-79
2005
Handle:
https://hdl.handle.net/2376/114048
Abstract
We show that the emptiness problem for two-way nondeterministic finite automata augmented with one reversal-bounded counter (i.e., the counter alternates between nondecreasing and nonincreasing modes for a fixed number of times) operating on bounded languages (i.e., subsets of
w
1
*
…
w
k
*
for some nonnull words
w
1
,
…
,
w
k
) is decidable, resolving an open problem. The proof is a rather involved reduction to the solution of a special class of Diophantine systems of degree 2 via a class of programs called two-phase programs.
Metrics
13 Record Views
Details
- Title
- On two-way nondeterministic finite automata with one reversal-bounded counter
- Creators
- Zhe Dang - School of Electrical Engineering and Computer Science, Washington State University, Pullman, WA 99164, USAOscar H Ibarra - Department of Computer Science, University of California, Santa Barbara, CA 93106, USAZhi-Wei Sun - Department of Mathematics, Nanjing University, Nanjing 210093, China
- Publication Details
- Theoretical computer science, Vol.330(1), pp.59-79
- Academic Unit
- Electrical Engineering and Computer Science, School of
- Publisher
- Elsevier B.V
- Identifiers
- 99900548227001842
- Language
- English
- Resource Type
- Journal article