The contribution discusses the accepting state complexity under various operations that preserve regular languages. The regular languages are exactly those languages that can be accepted by deterministic finite-state automata (DFA). The accepting state complexity of a language \(L\) is the minimal number of accepting states needed by some DFA to accept \(L\). It coincides with the number of accepting states in the unique (up to isomorphism) minimal DFA for \(L\). This line of research was started in [J. Dassow, J. Autom. Lang. Comb. 21, No. 1–2, 55–67 (2016; Zbl 1362.68134)] and is continued here for the operations that were not considered by Dassow. The worst-case behaviour of the accepting state complexity under a given operation \(f\) (like union, intersection, reversal) that preserves regular languages is given as follows. Given \(k\) regular languages \(L_1, \dotsc, L_k\) of given accepting state complexities \(c_1, \dotsc, c_k\), the task is to determine the range of possible accepting state complexities of the resulting language \(f(L_1, \dotsc, L_k)\) in terms of \(c_1, \dotsc, c_k\).
The accepting state complexity is investigated for intersection, symmetric difference, quotient, reversal and permutation of finite languages. Another focus in the contribution are magic numbers, which are numbers that are unobtainable as accepting state complexity for the resulting language. The general approach for most of those problems is a close inspection of the standard construction and identifying when the resulting DFA is actually already minimal (or which states are certainly equivalent or unreachable). A vast amount of experience for this approach exists due to the numerous publications on the (standard) state complexity, which considers the total number of states instead of just the number of accepting states. The accepting state complexity for nondeterministic finite-state automata (NFA) is also discussed, but since we need at most 2 accepting states for any regular language, the only question that remained was an exact characterization which regular languages have nondeterministic accepting state complexity 0 or 1. This is settled in the current contribution in the expected fashion: The only language that contains the empty word, but retains nondeterministic accepting state complexity 1 is the universal language.
Overall, the contribution is very well written. Examples, illustrations, and intuitions are generously provided. It should be very simple to understand it for anyone with some background in automata theory (specifically, minimization of DFA).