In this paper we investigate the minimality problem of \{DFAs\} by varying the set of final states. In other words, we are interested on how the choice of the final states can affect the minimality of the automata. The state-pair graph is a useful tool to investigate such a problem. The choice of a set of final states for the automaton A defines a coloring of the closed components of the state-pair graph and the minimality of A corresponds to a property of these colored components. A particular attention is devoted to the analysis of some extremal cases such as, for example, the automata that are minimal for any choice of the subset of final states F from the state set Q of the automaton (uniformly minimal automata), the automata that are minimal for any proper subset F of Q (almost uniformly minimal automata) and the automata that are never minimal, under any assignment of final states (never-minimal automata). More generally, we seek to characterize those families of automata and show that some of them are related to well-known objects in a different context (e.g. multiple-entry automata and Fischer covers of irreducible sofic shifts in Symbolic Dynamics). Next, we study the complexity of the related decision problems and show, in some cases, how to derive a polynomial algorithm. Finally, we pay particular attention to the relationship between the problem to decide if an automaton is never-minimal and the “syntactic monoid problem”.

Restivo, A., & Vaglica, R. (2012). Extremal minimality conditions on automata. THEORETICAL COMPUTER SCIENCE, 440–441, 73-84 [10.1016/j.tcs.2012.03.049].

Extremal minimality conditions on automata

RESTIVO, Antonio;VAGLICA, Roberto
2012

Abstract

In this paper we investigate the minimality problem of \{DFAs\} by varying the set of final states. In other words, we are interested on how the choice of the final states can affect the minimality of the automata. The state-pair graph is a useful tool to investigate such a problem. The choice of a set of final states for the automaton A defines a coloring of the closed components of the state-pair graph and the minimality of A corresponds to a property of these colored components. A particular attention is devoted to the analysis of some extremal cases such as, for example, the automata that are minimal for any choice of the subset of final states F from the state set Q of the automaton (uniformly minimal automata), the automata that are minimal for any proper subset F of Q (almost uniformly minimal automata) and the automata that are never minimal, under any assignment of final states (never-minimal automata). More generally, we seek to characterize those families of automata and show that some of them are related to well-known objects in a different context (e.g. multiple-entry automata and Fischer covers of irreducible sofic shifts in Symbolic Dynamics). Next, we study the complexity of the related decision problems and show, in some cases, how to derive a polynomial algorithm. Finally, we pay particular attention to the relationship between the problem to decide if an automaton is never-minimal and the “syntactic monoid problem”.
Settore INF/01 - Informatica
Restivo, A., & Vaglica, R. (2012). Extremal minimality conditions on automata. THEORETICAL COMPUTER SCIENCE, 440–441, 73-84 [10.1016/j.tcs.2012.03.049].
File in questo prodotto:
File Dimensione Formato  
Extremal minimality conditions on automata 2012.pdf

Solo gestori archvio

Descrizione: Articolo principale
Dimensione 363.29 kB
Formato Adobe PDF
363.29 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: http://hdl.handle.net/10447/73714
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact