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

Castiglione, G., Restivo, A., Sciortino, M. (2012). Nondeterministic Moore automata and Brzozowski's minimization algorithm. THEORETICAL COMPUTER SCIENCE, 450, 81-91 [10.1016/j.tcs.2012.04.029].

Nondeterministic Moore automata and Brzozowski's minimization algorithm

CASTIGLIONE, Giuseppa;RESTIVO, Antonio;SCIORTINO, Marinella
2012-01-01

Abstract

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. 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.
Settore INF/01 - Informatica
Castiglione, G., Restivo, A., Sciortino, M. (2012). Nondeterministic Moore automata and Brzozowski's minimization algorithm. THEORETICAL COMPUTER SCIENCE, 450, 81-91 [10.1016/j.tcs.2012.04.029].
File in questo prodotto:
File Dimensione Formato  
TheorCompSci2012.pdf

Solo gestori archvio

Dimensione 410.07 kB
Formato Adobe PDF
410.07 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/64506
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact