Mirror images and schemes for the maximal complexity of nondeterminism (Q2893313)

The contribution investigates when the subset construction, which given a finite automaton constructs an equivalent deterministic finite automaton, induces the maximal, exponential blow-up. More precisely, the author investigates schemes of deterministic finite automata, whose reversal, which in general is a potentially non-deterministic finite automaton accepting the mirror image of the language accepted by the original automaton, yields the mentioned maximal blow-up when used in the subset construction. A scheme here is a general automaton layout description (given the number \(n\) of states it specifies the transitions between the states), in which the selection of the initial state and the selection of the final states is left open. In fact, such schemes are investigated such that for any (non-trivial) selection of the initial state and the final states we obtain a maximal blow-up.NEWLINENEWLINEThe author presents an algebraic approach to this problem. He first recalls the 3-symbol Lupanov automaton, which was the inspiration for many of the subsequently discovered automata that induce the maximal blow-up. For this case (with at least 3 symbols) solutions to the maximal blow-up problem for schemes are essentially known and quickly recalled. Then the author develops an algebraic theory that explains why the maximal blow-up occurs. In particular, it reduces the maximal blow-up problem for schemes to the completeness of a set of subset functions. This part is rather straightforward, but translates the problem into a new setting. This theory is then applied to the binary case which was still partially open. The obtained complete set of subset functions thus yields a scheme over a binary alphabet that induces the maximal blow-up. Finally, the author recalls an existing approach jointly with the late Derrick Wood [\textit{A. Salomaa} et al., Theor. Comput. Sci. 320, No. 2--3, 315--329 (2004; Zbl 1068.68078)]. This proposal already yields a partial solution, which is acknowledged and thoroughly discussed.NEWLINENEWLINEThe material is rather basic, and examples illustrate the core notions well. It should be accessible to all mathematically mature readers that have at least a minimal background in finite automata theory. The paper is well written and efficiently communicates its ideas. The author carefully places his contribution into the existing literature and acknowledges the existing results and relates them to his results.