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.
2008
Developments in Language Theory 2008
Kyoto, Giappone
2008
12
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.
Proceedings (atti dei congressi)
Bassino, F; Giambruno, L; Nicaud, C;
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/40308
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact