3
$\begingroup$

Given a regular language (by a sparse or dense matrix describing the graph of the NFA) (initially the description was supposed to be a regular expression) and a word, can the problem whether the word belongs to the regular language be decided on a (random access) alternating Turing machine in a logarithmic amount of computation time? (The many links above try to compensate for the fact that I didn't find a nice self-contained description of ALogTime.) The length of the input is the length of the description of the regular language plus the length of the word.

$\endgroup$
3
$\begingroup$

If the regular expression is not fixed, it is rather doubtful that your problem belongs to ALOGTIME. However, the phrase word problem usually refers to a fixed setting, which in this case means that the regular language is fixed.

If the regular language is fixed, this is apparently shown in Barrington's famous paper. Alternatively, you can describe a logtime game for deciding the word problem for regular languages. The game starts with the YES player stating the final (accepting) state and the state at the middle (the initial state is of course fixed). The NO player then chooses one of the halves, and the game continues until it comes down to a word of length 1, in which case the problem can be settled by examining one character of the input.

$\endgroup$
  • $\begingroup$ If I would include the (sparse or dense matrix describing the graph of the) NFA instead of the regular expression, then it seems that checking the last step (in NLogTime) would be possible. Do you agree? (I only wrote regular expression instead of regular language, because it seemed more convenient and explicit. I didn't intent this to have any impact on the actual answer to the question.) $\endgroup$ – Thomas Klimpel Jan 28 '16 at 9:40
  • $\begingroup$ Yes, this sounds reasonable. $\endgroup$ – Yuval Filmus Jan 28 '16 at 9:41
  • $\begingroup$ If the NFA (or regular expression) is not fixed, then the size of a state is $\log n$. Even so the algorithm above will still work perfectly well, it will take more than $\log n$ time. Which is a good thing, since the NFA membership problem is NL-complete. (I added a community wiki answer below, which explains why this observation is nearly trivial.) $\endgroup$ – Thomas Klimpel Sep 4 '17 at 6:33
2
$\begingroup$

If (the regular expression or) NFA is not fixed, then the problem is NL-complete. So if the problem would be in ALogTime, then ALogTime=L=NL, which is an open problem.

It is clear that the problem is in NL, we only need one pointer into the word on which the NFA runs, the current (and guessed next) state of the NFA (its size is $\log |A|$, if $A$ is a description of the NFA by a list of possible transitions), and a pointer into the description of the NFA.

To see that it is NL complete, reduce reachability to the NFA membership problem over the unary language. Use the given digraph as NFA, and add a self-loop to the target node whose reachability is being checked. Let the source node be only state in the set of initial states, the target node be the only state in the set of (accepting) final states, and check whether this NFA accepts the word $1^n$, where $n$ is the number of nodes of the given digraph (which is also the number of states of the constructed NFA).

The reason why Yuval Filmus' algorithm (explained in his answer above, together with the comments below) doesn't solve this problem in ALogTime is not that the last step would not work. That checking can indeed be done in NLogTime. But the size of a state is $\log n$ if the NFA is not fixed, and hence the algorithm takes $\log^2 n$ time instead of $\log n$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.