We prove that, for the uniform distribution over all sets X of m (that is a fixed integer) non-empty words whose sum of lengths is n, D_X, one of the usual deterministic automata recognizing X*, has in average O(n) states and that the state complexity of X* is Theta(n). We also show that the average time complexity of the computation of the automaton D_X is O(n log n), when the alphabet is of size at least three.
Bassino, F., Giambruno, L., Nicaud, C. (2008). The average state complexity of the star of a finite set of words is linear.. ??????? it.cilea.surplus.oa.citation.tipologie.CitationProceedings.prensentedAt ??????? Developments in Language Theory 2008, Kyoto, Giappone.
The average state complexity of the star of a finite set of words is linear.
GIAMBRUNO, Laura;
2008-01-01
Abstract
We prove that, for the uniform distribution over all sets X of m (that is a fixed integer) non-empty words whose sum of lengths is n, D_X, one of the usual deterministic automata recognizing X*, has in average O(n) states and that the state complexity of X* is Theta(n). We also show that the average time complexity of the computation of the automaton D_X is O(n log n), when the alphabet is of size at least three.
| File | Dimensione | Formato | |
|---|---|---|---|
|
dlt2008.pdf
Solo gestori archvio
Descrizione: articolo principale
Dimensione
173.97 kB
Formato
Adobe PDF
|
173.97 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.
