Let n be a positive integer, a word w is n-compressing for a finite deterministic automaton if its natural action reduces the image of the automaton state set by at least n states. A word w is n-collapsing if it is n-compressible for all deterministic finite automata that admit n-compressing words. We improve the known theoretical bound for the lenght of the shortest 2-collapsing word an a finite alphabet. Then we produce shorter 2-collapsing and 2-synchronizing words over alphabets of 4 and 5 elements.
On the length of shortest 2-collapsing words
CHERUBINI, ALESSANDRA;
2009-01-01
Abstract
Let n be a positive integer, a word w is n-compressing for a finite deterministic automaton if its natural action reduces the image of the automaton state set by at least n states. A word w is n-collapsing if it is n-compressible for all deterministic finite automata that admit n-compressing words. We improve the known theoretical bound for the lenght of the shortest 2-collapsing word an a finite alphabet. Then we produce shorter 2-collapsing and 2-synchronizing words over alphabets of 4 and 5 elements.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
bound_2-collapsing.pdf
Accesso riservato
:
Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione
218.26 kB
Formato
Adobe PDF
|
218.26 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
