Deciding determinism of regular languages
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)].
scientific article; zbMATH DE number 6478532
scientific article