Extremal minimality conditions on automata

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