6533b7d9fe1ef96bd126d217
RESEARCH PRODUCT
The average state complexity of rational operations on finite languages is linear
F BassinoC. NicaudLaura Giambrunosubject
finite languages regular operations automata state complexity average case analysisSettore INF/01 - Informaticadescription
Considering the uniform distribution on sets of m non-empty words whose sum of lengths is n, we establish that the average state complexities of the rational operations are asymptotically linear.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2010-01-01 |