The 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.
Restivo, A., Vaglica, R. (2012). A graph theoretic approach to automata minimality. THEORETICAL COMPUTER SCIENCE, 429, 282-291 [10.1016/j.tcs.2011.12.049].
A graph theoretic approach to automata minimality
RESTIVO, Antonio;VAGLICA, Roberto
2012-01-01
Abstract
The 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.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
A graph theoretic approach to automata minimality_TCS2012.pdf
Solo gestori archvio
Descrizione: Articolo principale
Dimensione
344.75 kB
Formato
Adobe PDF
|
344.75 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.
