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/}
}
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/