The average state complexity of the star of a finite set of words is linear.

Laura Giambruno, Frédérique Bassino, Cyril Nicaud

Risultato della ricerca: Other

2 Citazioni (Scopus)

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.
Lingua originaleEnglish
Numero di pagine12
Stato di pubblicazionePublished - 2008

All Science Journal Classification (ASJC) codes

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???

Fingerprint

Entra nei temi di ricerca di 'The average state complexity of the star of a finite set of words is linear.'. Insieme formano una fingerprint unica.

Cita questo