The synchronization problem is investigated for a new class of deterministic automata called strongly transitive. We find an upper bound for the length of the shortest synchronizing word of a synchronizing strongly transitive n-state automaton. An extension to unambiguous automata is also considered.
Strongly transitive automata and the Cerny conjecture
CARPI, Arturo;
2009
Abstract
The synchronization problem is investigated for a new class of deterministic automata called strongly transitive. We find an upper bound for the length of the shortest synchronizing word of a synchronizing strongly transitive n-state automaton. An extension to unambiguous automata is also considered.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
