\((k,l)\)-unambiguity and quasi-deterministic structures.

*(English)*Zbl 1439.68012The contribution investigates \((k, l)\)-unambiguous automata and their theoretical properties. In particular, the authors demonstrate a specific structure that can be used to efficiently solve the
membership problem of such automata. In addition, they discuss several methods to reduce the size of those automata in order to make the tests even more efficient. They show that their quasi-deterministic structures can be exponentially more succinct than the classical deterministic finite-state automaton. More precisely, a \((k, l)\)-unambiguous automaton is a finite-state automaton that when reading words of \(k\) letters the different paths that are possible need to rejoin after at most \(l\) letters. This notion generalizes the \(k\)-lookahead notion, in which the rejoin is enforced after reading just a single symbol.

The investigation is motivated from the regular expressions permitted in DTDs. They are allowed to be 1-unambiguous, which means that the position automaton corresponding to the expression should be deterministic. The aim is to extend the permitted regular expressions, while still retaining efficient evaluation. To this end, the authors introduce the mentioned notion of \((k, l)\)-unambiguity and then show that any automaton that has this property can be translated into a quasi-deterministic structure, which then allows efficient evaluation of the membership problem. Next, the authors demonstrate that unreachable states in the structure can be removed and they introduce an equivalence relation, which can also effectively be computed, that permits the reduction of the structure. This approach follows essentially the classical minimization techniques. Finally, the authors showcase a regular expression, which requires an exponentially large deterministic finite-state automaton, but can be represented by a quasi-deterministic structure of polynomial size.

Overall, the paper is well written and can easily be understood by anyone familiar with regular expressions and finite-state automata. All needed notions and notations are carefully introduced and illustrated by means of examples. Intuition is generously provided and suitable graphical illustrations support the reader.

The investigation is motivated from the regular expressions permitted in DTDs. They are allowed to be 1-unambiguous, which means that the position automaton corresponding to the expression should be deterministic. The aim is to extend the permitted regular expressions, while still retaining efficient evaluation. To this end, the authors introduce the mentioned notion of \((k, l)\)-unambiguity and then show that any automaton that has this property can be translated into a quasi-deterministic structure, which then allows efficient evaluation of the membership problem. Next, the authors demonstrate that unreachable states in the structure can be removed and they introduce an equivalence relation, which can also effectively be computed, that permits the reduction of the structure. This approach follows essentially the classical minimization techniques. Finally, the authors showcase a regular expression, which requires an exponentially large deterministic finite-state automaton, but can be represented by a quasi-deterministic structure of polynomial size.

Overall, the paper is well written and can easily be understood by anyone familiar with regular expressions and finite-state automata. All needed notions and notations are carefully introduced and illustrated by means of examples. Intuition is generously provided and suitable graphical illustrations support the reader.

Reviewer: Andreas Maletti (Leipzig)

##### MSC:

68Q45 | Formal languages and automata |