Let k be a positive integer. A finite deterministic automaton is called k-compressible if the size of image of state set under the natural action of some word w is reduced by k, w is then called a k-compressing word for the automaton. A word on an finite alphabet A is called k-collapsing it is k-compressing for each k-compressible automaton on the alphabet A. A word on the alphabet A is called k-synchronizing if it is a reset word for all synchronizing automata with k+1 states and input alphabet A. The aim of this work is to give the motivations of the interest in these words and to provide an overview of some results in this area that is at the border of combinatorics, algebra and theoretical computer science.
Synchronizing and collapsing words
CHERUBINI, ALESSANDRA
2007-01-01
Abstract
Let k be a positive integer. A finite deterministic automaton is called k-compressible if the size of image of state set under the natural action of some word w is reduced by k, w is then called a k-compressing word for the automaton. A word on an finite alphabet A is called k-collapsing it is k-compressing for each k-compressible automaton on the alphabet A. A word on the alphabet A is called k-synchronizing if it is a reset word for all synchronizing automata with k+1 states and input alphabet A. The aim of this work is to give the motivations of the interest in these words and to provide an overview of some results in this area that is at the border of combinatorics, algebra and theoretical computer science.File | Dimensione | Formato | |
---|---|---|---|
Tibiletti.pdf
Accesso riservato
:
Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione
188.08 kB
Formato
Adobe PDF
|
188.08 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.