### Abstract

Lingua originale | English |
---|---|

pagine (da-a) | 73-84 |

Numero di pagine | 12 |

Rivista | Theoretical Computer Science |

Volume | 440–441 |

Stato di pubblicazione | Published - 2012 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

### Cita questo

*Theoretical Computer Science*,

*440–441*, 73-84.

**Extremal minimality conditions on automata.** / Vaglica, Roberto; Restivo, Antonio.

Risultato della ricerca: Article

*Theoretical Computer Science*, vol. 440–441, pagg. 73-84.

}

TY - JOUR

T1 - Extremal minimality conditions on automata

AU - Vaglica, Roberto

AU - Restivo, Antonio

PY - 2012

Y1 - 2012

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

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

UR - http://hdl.handle.net/10447/73714

M3 - Article

VL - 440–441

SP - 73

EP - 84

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -