Nondeterministic Moore automata and Brzozowski's minimization algorithm (Q442154)

A Moore automaton is a finite state machine where states are labeled by output symbols. Such an automaton defines the function that maps an input string to the output symbol labeling the last state of the run. This paper considers non-deterministic variants. The authors hence consider non-deterministic Moore automata (NMA), in which there could be many possible next states for some input symbol and in which all states don't necessarily have to be labeled by an output symbol. In order to still be able to define a function, the authors introduce \textit{coherent} NMA, which furthermore satisfy the following two properties. First, if an input word has a run, then there is one ending on a state labeled by an output symbol. Secondly, for any input word, all runs ending on a state labeled by an output symbol ends on a states labeled by the \textit{same} output symbol. The main result of the paper is a variant of \textit{J. A. Brzozowski}'s algorithm [in: Proc. Symp. Math. Theor. Automata, New York 1962, 529--561 (1963; Zbl 0116.33605)] to produce an equivalent deterministic Moore automaton with minimal number of states, from a coherent NMA. As for the case of the original Brzozowski algorithm, the time complexity is here also exponential in the worst case. Finally the authors consider \textit{semi-coherent} NMA, defined as coherent NMA but keeping only the second property. They show that semi-coherent NMA are more expressible than coherent (in terms of function definition) but that nevertheless their algorithm still produces a minimal deterministic equivalent automaton.