6533b7d8fe1ef96bd126b790

RESEARCH PRODUCT

Nondeterministic Moore automata and Brzozowski's minimization algorithm

Giusi CastiglioneMarinella SciortinoAntonio Restivo

subject

Discrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESGeneral Computer ScienceBrzozowski’s minimization algorithmSettore INF/01 - InformaticaPowerset constructionAutomata minimizationBüchi automatonNonlinear Sciences::Cellular Automata and Lattice GasesTheoretical Computer ScienceNondeterministic algorithmDeterministic finite automatonTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDFA minimizationDeterministic automatonTwo-way deterministic finite automatonNondeterministic finite automatonBrzozowski's minimization algorithmComputer Science::Formal Languages and Automata TheoryComputer Science(all)MathematicsNondeterministic Moore automata

description

AbstractMoore automata represent a model that has many applications. In this paper we define a notion of coherent nondeterministic Moore automaton (NMA) and show that such a model has the same computational power of the classical deterministic Moore automaton. We consider also the problem of constructing the minimal deterministic Moore automaton equivalent to a given NMA. We propose an algorithm that is a variant of Brzozowski’s minimization algorithm in the sense that it is essentially structured as reverse operation and subset construction performed twice. Moreover, we explore more general classes of NMA and analyze the applicability of the algorithm. For some of such classes the algorithm does not return the minimal equivalent deterministic automaton.

yearjournalcountryeditionlanguage
2012-09-01
10.1016/j.tcs.2012.04.029http://hdl.handle.net/10447/64506