Nondeterministic Moore automata and Brzozowski's minimization algorithm

DOI10.1016/J.TCS.2012.04.029MaRDI QIDQ442154zbMATH OpenOpenAlexFDO

Authors Antonio Restivo, M. Sciortino, G. Castiglione

Publication date 9 August 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.04.029

zbMATH Keywords

automata minimizationBrzozowski's minimization algorithmnondeterministic Moore automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

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.NEWLINENEWLINEThe 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.NEWLINENEWLINEThe 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.NEWLINENEWLINEFinally 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.

Recommendations

• Nondeterministic Moore automata and Brzozowski's algorithm
• Brzozowski's minimization algorithm -- more robust than expected (extended abstract)
• Algebra-coalgebra duality in Brzozowski's minimization algorithm
• Minimisation of automata
• Brzozowski's algorithm (co)algebraically

Cites work

• A challenging family of automata for classical minimization algorithms
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Experimental Evaluation of Classical Automata Constructions
• Hopcroft's algorithm and tree-like automata
• scientific article; zbMATH DE number 1361134 (Why is no real title available?)
• scientific article; zbMATH DE number 1543070 (Why is no real title available?)
• scientific article; zbMATH DE number 798342 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 3264952 (Why is no real title available?)
• scientific article; zbMATH DE number 3420624 (Why is no real title available?)
• scientific article; zbMATH DE number 3189697 (Why is no real title available?)
• Lattice Automata
• Minimization algorithms for sequential transducers
• Minimizing deterministic lattice automata
• On extremal cases of Hopcroft's algorithm
• On the State Minimization of Nondeterministic Finite Automata
• Optimal simulation of self-verifying automata by deterministic automata
• Weighted automata algorithms

Cited in

(1)

• Nondeterministic Moore automata and Brzozowski's algorithm

Describes a project that uses

Uses Software

• fsm2

This page was built for publication: Nondeterministic Moore automata and Brzozowski's minimization algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q442154)