6533b833fe1ef96bd129b851

RESEARCH PRODUCT

Automata with Extremal Minimality Conditions

Roberto VaglicaAntonio Restivo

subject

Discrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESPowerset constructionBüchi automatonω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesCombinatoricsTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDFA minimizationDeterministic automatonQuantum finite automataTwo-way deterministic finite automatonNondeterministic finite automatonComputer Science::Formal Languages and Automata TheoryAutomata MinimizationMathematics

description

It is well known that the minimality of a deterministic finite automaton (DFA) depends on the set of final states. In this paper we study the minimality of a strongly connected DFA by varying the set of final states. We consider, in particular, some extremal cases. A strongly connected DFA is called uniformly minimal if it is minimal, for any choice of the set of final states. It is called never-minimal if it is not minimal, for any choice of the set of final states. We show that there exists an infinite family of uniformly minimal automata and that there exists an infinite family of never-minimal automata. Some properties of these automata are investigated and, in particular, we consider the complexity of the problem to decide whether an automaton is uniformly minimal or neverminimal.

yearjournalcountryeditionlanguage
2010-01-01
https://doi.org/10.1007/978-3-642-14455-4_36