Unary finite automata vs. arithmetic progressions

Details Unary finite automata vs. arithmetic progressions Unary finite automata vs. arithmetic progressions

2008-12-06

arxiv.org/abs/0812.1291v1

Computer Science

Computational Complexity

Journal paper submitted

Scientific paper

We point out a subtle error in the proof of Chrobak's theorem that every unary NFA can be represented as a union of arithmetic progressions that is at most quadratically large. We propose a correction for this and show how Martinez's polynomial time algorithm, which realizes Chrobak's theorem, can be made correct accordingly. We also show that Martinez's algorithm cannot be improved to have logarithmic space, unless L = NL.

Affiliated with

Also associated with

No associations

Rating

Unary finite automata vs. arithmetic progressions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Unary finite automata vs. arithmetic progressions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unary finite automata vs. arithmetic progressions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-719780