6533b857fe1ef96bd12b3a81

RESEARCH PRODUCT

Nondeterministic Moore Automata and Brzozowski’s Algorithm

Antonio RestivoGiusi CastiglioneMarinella Sciortino

subject

Discrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESSettore INF/01 - InformaticaPowerset constructionBüchi automatonNonlinear Sciences::Cellular Automata and Lattice GasesNondeterministic algorithmTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonDFA minimizationDeterministic automatonTwo-way deterministic finite automatonMoore automata minimization Brzozowski'algorithmNondeterministic finite automatonAlgorithmComputer Science::Formal Languages and Automata TheoryMathematics

description

Moore 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. In this paper we propose an algorithm that is a variant of Brzozowski's algorithm in the sense that it is essentially structured as reverse operation and subset construction performed twice.

yearjournalcountryeditionlanguage
2011-01-01
https://doi.org/10.1007/978-3-642-22256-6_9