RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1989 Volume 1, Issue 4, Pages 12–16 (Mi dm936)

Upper bounds on finite-automaton complexity for generalized regular expressions in a one-letter alphabet

Z. R. Dang


Abstract: We compare the complexity of specifying a regular event by a finite automaton and a generalized regular expression. The measure of complexity of the automaton is the number of its states $G$, and the measure of complexity of the generalized regular expression is its refined length $\alpha$. We show that for generalized (having operations of set-theoretic complementation and intersection) regular expressions in a one-letter alphabet, $G\leqslant 3^\alpha$.

UDC: 519.95

Received: 20.12.1988



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024