Deciding determinism of regular languages (Q493651)

The paper deals with the problem of deciding whether a given regular language \(L\) can be described by a deterministic (also called one-unambiguous) regular expression, that is, a regular expression such that each occurrence of a letter in any word from \(L\) can be uniquely matched to a symbol in this expression, without looking ahead in the word. The algorithm for this problem due to \textit{A. Brüggemann-Klein} and \textit{D. Wood} [Inf. Comput. 142, No. 2, 182--206 (1998; Zbl 0912.68112)] is modified so that recursive calls are avoided. In this way it is shown that the problem is NL-complete if input languages are given by deterministic finite automata and the size of the alphabet is either constant or logarithmic. Using the same approach, it is also proved that the problem can be solved in quadratic space if input languages are given by nondeterministic finite automata or regular expressions, thereby improving the result of \textit{W. Czerwiński} et al. [Lect. Notes Comput. Sci. 7794, 289--304 (2013; Zbl 1260.68199)].