Computer Science – Formal Languages and Automata Theory
Scientific paper
2009-05-08
Computer Science
Formal Languages and Automata Theory
18 pages. The paper will appear on the Journal of Automata, Languages and Combinatorics
Scientific paper
In this paper we consider the time and the crossing sequence complexities of one-tape off-line Turing machines. We show that the running time of each nondeterministic machine accepting a nonregular language must grow at least as n\log n, in the case all accepting computations are considered (accept measure). We also prove that the maximal length of the crossing sequences used in accepting computations must grow at least as \log n. On the other hand, it is known that if the time is measured considering, for each accepted string, only the faster accepting computation (weak measure), then there exist nonregular languages accepted in linear time. We prove that under this measure, each accepting computation should exhibit a crossing sequence of length at least \log\log n. We also present efficient implementations of algorithms accepting some unary nonregular languages.
No associations
LandOfFree
Nondeterministic one-tape off-line Turing machines and their time complexity 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 Nondeterministic one-tape off-line Turing machines and their time complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nondeterministic one-tape off-line Turing machines and their time complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-703774