Geodesic
Upper bounds on finite-automaton complexity for generalized regular expressions in a~one-letter alphabet
Diskretnaya Matematika, Tome 1 (1989) no. 4, pp. 12-16

Voir la notice de l'article provenant de la source Math-Net.Ru

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$. 
@article{DM_1989_1_4_a1,
     author = {Z. R. Dang},
     title = {Upper bounds on finite-automaton complexity for generalized regular expressions in a~one-letter alphabet},
     journal = {Diskretnaya Matematika},
     pages = {12--16},
     publisher = {mathdoc},
     volume = {1},
     number = {4},
     year = {1989},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1989_1_4_a1/}
}
TY  - JOUR
AU  - Z. R. Dang
TI  - Upper bounds on finite-automaton complexity for generalized regular expressions in a~one-letter alphabet
JO  - Diskretnaya Matematika
PY  - 1989
SP  - 12
EP  - 16
VL  - 1
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1989_1_4_a1/
LA  - ru
ID  - DM_1989_1_4_a1
ER  - 
%0 Journal Article
%A Z. R. Dang
%T Upper bounds on finite-automaton complexity for generalized regular expressions in a~one-letter alphabet
%J Diskretnaya Matematika
%D 1989
%P 12-16
%V 1
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1989_1_4_a1/
%G ru
%F DM_1989_1_4_a1
Z. R. Dang. Upper bounds on finite-automaton complexity for generalized regular expressions in a~one-letter alphabet. Diskretnaya Matematika, Tome 1 (1989) no. 4, pp. 12-16. http://geodesic.mathdoc.fr/item/DM_1989_1_4_a1/