6533b7cefe1ef96bd1257140
RESEARCH PRODUCT
The Average State Complexity of the Star of a Finite Set of Words Is Linear
Frédérique BassinoCyril NicaudLaura Giambrunosubject
Uniform distribution (continuous)ComputationStar (game theory)0102 computer and information sciences02 engineering and technology[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]01 natural sciencesCombinatoricsInteger0202 electrical engineering electronic engineering information engineeringTime complexityFinite setMathematicsstar operationDiscrete mathematicsaverage case analysistate complexity16. Peace & justiceBinary logarithm[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]automatonState complexity010201 computation theory & mathematicsfinite language020201 artificial intelligence & image processingComputer Science::Formal Languages and Automata Theorydescription
We prove that, for the uniform distribution over all sets Xof m(that is a fixed integer) non-empty words whose sum of lengths is n, $\mathcal{D}_X$, one of the usual deterministic automata recognizing X*, has on average $\mathcal{O}(n)$ states and that the average state complexity of X*is i¾?(n). We also show that the average time complexity of the computation of the automaton $\mathcal{D}_X$ is $\mathcal{O}(n\log n)$, when the alphabet is of size at least three.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2008-01-01 |