Is the word problem for regular languages in ALogTime?

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.

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.

StackExchange Computer Science Q#52379, answer score: 4