The average state complexity of rational operations on finite languages is linear

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

Risultato della ricerca: Articlepeer review

5 Citazioni (Scopus)

Abstract

Considering the uniform distribution on sets of m non-empty words whose sum of lengthsis n, we establish that the average state complexities of the rational operations areasymptotically linear.
Lingua originaleEnglish
pagine (da-a)495-516
Numero di pagine21
RivistaInternational Journal of Foundations of Computer Science
Volume21
Stato di pubblicazionePublished - 2010

All Science Journal Classification (ASJC) codes

  • ???subjectarea.asjc.1700.1701???

Cita questo