Geodesic
Cardinality estimates for some classes of regular languages
Diskretnaya Matematika, Tome 27 (2015) no. 2, pp. 3-21

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

We consider a method that modifies regular expressions in order to solve the “exponential explosion” problem on the number of states of the finite automaton that recognizes a set of regular languages defined by the union of regular expressions of the form $.{*}$R$_1.{*}$R$_2.{*}$, where R$_1$ and R$_2$ are arbitrary regular expressions. We estimate the growth functions of regular languages from a subclass of the described class of regular languages and propose a method for estimation of relative growth of the number of words for the modification of a language defined by a pair of regular expressions. We also analyse practical efficiency of the proposed modification method and estimation method for the case of regular expressions from the system Snort.
Keywords: finite automata, regular expressions, intrusion detection systems. 
@article{DM_2015_27_2_a0,
     author = {D. E. Alexandrov},
     title = {Cardinality estimates for some classes of regular languages},
     journal = {Diskretnaya Matematika},
     pages = {3--21},
     publisher = {mathdoc},
     volume = {27},
     number = {2},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2015_27_2_a0/}
}
TY  - JOUR
AU  - D. E. Alexandrov
TI  - Cardinality estimates for some classes of regular languages
JO  - Diskretnaya Matematika
PY  - 2015
SP  - 3
EP  - 21
VL  - 27
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2015_27_2_a0/
LA  - ru
ID  - DM_2015_27_2_a0
ER  - 
%0 Journal Article
%A D. E. Alexandrov
%T Cardinality estimates for some classes of regular languages
%J Diskretnaya Matematika
%D 2015
%P 3-21
%V 27
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2015_27_2_a0/
%G ru
%F DM_2015_27_2_a0
D. E. Alexandrov. Cardinality estimates for some classes of regular languages. Diskretnaya Matematika, Tome 27 (2015) no. 2, pp. 3-21. http://geodesic.mathdoc.fr/item/DM_2015_27_2_a0/