6533b7dcfe1ef96bd1273456

RESEARCH PRODUCT

A graph theoretic approach to automata minimality

Antonio RestivoRoberto Vaglica

subject

Discrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESSettore INF/01 - InformaticaGeneral Computer Sciencegraph theoryContinuous automatonTimed automatonPushdown automatonBüchi automatonautomata minimalityNonlinear Sciences::Cellular Automata and Lattice GasesTheoretical Computer ScienceAutomatonCombinatoricsCardinalityDeterministic automatonTwo-way deterministic finite automatonComputer Science::Formal Languages and Automata TheoryMathematics

description

AbstractThe paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F. We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms.

yearjournalcountryeditionlanguage
2012-04-01Theoretical Computer Science
10.1016/j.tcs.2011.12.049http://dx.doi.org/10.1016/j.tcs.2011.12.049