Average State Complexity of Operations on Unary Automata - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 1999

Average State Complexity of Operations on Unary Automata

Résumé

Define the complexity of a regular language as the number of states of its minimal automaton. Let A (respectively A') be an n-state (resp. n'-state) deterministic and connected unary automaton. Our main results can be summarized as follows: 1. The probability that A is minimal tends toward 1/2 when n tends toward infinity 2. The average complexity of L(A) is equivalent to n 3. The average complexity of L(A)∩L(A') is equivalent to (3ζ(3)/2π²)nn', where ζ is the Riemann "zeta"-function. 4. The average complexity of L(A) is bounded by a constant, 5. If n ≤ n' ≤ P(n), for some polynomial P, the average complexity of L(A)L(A') is bounded by a constant (depending on P). Remark that results 3, 4 and 5 differ perceptibly from the corresponding worst case complexities, which are nn' for intersection, (n-1)²+1 for star and nn' for concatenation product.

Dates et versions

hal-00620109 , version 1 (07-09-2011)

Identifiants

Citer

Cyril Nicaud. Average State Complexity of Operations on Unary Automata. MFCS 1999, Sep 1999, Szklarska Poreba, Poland, Poland. pp.231-240, ⟨10.1007/3-540-48340-3_21⟩. ⟨hal-00620109⟩

Collections

UNIV-PARIS7 CNRS
78 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More