Geodesic
Disambiguation of regular expressions with backreferences via term rewriting
Modelirovanie i analiz informacionnyh sistem, Tome 31 (2024) no. 4, pp. 426-445

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

In this paper we focus on regular expressions with acyclic backreferences and treat them as a semiring satisfying certain theorems of Kleene algebra. Using these theorems as term rewriting rules, we introduce an algorithm for memory disambiguation of regular expressions. Furthermore, we demonstrate that the class of regexes with acyclic backreferences is closed under language reversal, in contrast to the generic backref-regexes, and provide the reversal algorithm, based on the disambiguation procedure. The results of our experiments revealed that, in certain cases, the matching time was significantly reduced when using the reversed expressions compared to the initial ones.
Keywords: extended regular expression, backreferences, Kleene algebra, capture group, reversal
Mots-clés : disambiguation. 
@article{MAIS_2024_31_4_a2,
     author = {D. N. Ismagilova and A. N. Nepeivoda},
     title = {Disambiguation of regular expressions with backreferences via term rewriting},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {426--445},
     publisher = {mathdoc},
     volume = {31},
     number = {4},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2024_31_4_a2/}
}
TY  - JOUR
AU  - D. N. Ismagilova
AU  - A. N. Nepeivoda
TI  - Disambiguation of regular expressions with backreferences via term rewriting
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2024
SP  - 426
EP  - 445
VL  - 31
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2024_31_4_a2/
LA  - en
ID  - MAIS_2024_31_4_a2
ER  - 
%0 Journal Article
%A D. N. Ismagilova
%A A. N. Nepeivoda
%T Disambiguation of regular expressions with backreferences via term rewriting
%J Modelirovanie i analiz informacionnyh sistem
%D 2024
%P 426-445
%V 31
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2024_31_4_a2/
%G en
%F MAIS_2024_31_4_a2
D. N. Ismagilova; A. N. Nepeivoda. Disambiguation of regular expressions with backreferences via term rewriting. Modelirovanie i analiz informacionnyh sistem, Tome 31 (2024) no. 4, pp. 426-445. http://geodesic.mathdoc.fr/item/MAIS_2024_31_4_a2/