On expressive power of regular expressions with subroutine calls and lookaround assertions

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F23%3A00370348" target="_blank" >RIV/68407700:21240/23:00370348 - isvavai.cz</a>

Result on the web

<a href="https://www.stringology.org/papers/PSC2023.pdf#page=76" target="_blank" >https://www.stringology.org/papers/PSC2023.pdf#page=76</a>

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

On expressive power of regular expressions with subroutine calls and lookaround assertions

Original language description

Many regular expression engines employ syntactical extensions to provide simple, expressive support for real-world needs. These features are subroutine calls, zero-width lookaround assertions, DEFINE rules, and named parenthesised expressions. A subroutine call executes a specified subpattern where the call is placed, possibly recursively. Lookaround assertions are either lookahead or lookbehind: a lookahead is a conditional within a subpattern: when it fails, the match at the current position of the whole subpattern fails, while a lookahead itself does not consume any input; a lookbehind works as a lookahead except it checks the input prior to the current position. A DEFINE rule introduces a subpattern for use by a subroutine call, while not involved in matching where the rule is placed. A named parenthesised expression can be executed by its name in addition to the parenthesis number. This paper presents a formalisation of subroutine calls, DEFINE rules, and named parenthesised expressions using the matching relation while attempting to mimic the behaviour of real-world regular expression engines. Also, we give an alternative constructive proof of equivalence of expressive power of regular expressions extended with subroutine calls and the class of context-free languages: a conversion between such expressions and context-free grammars. Finally, the question of whether regular expressions with operations lookaround assertion combined with subroutine call have greater expressive power than expressions with only subroutine call is answered positively.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the Prague Stringology Conference 2023

ISBN

978-80-01-07206-6

ISSN

—

e-ISSN

—

Number of pages

15

Pages from-to

68-82

Publisher name

CESKE VYSOKE UCENI TECHNICKE V PRAZE

Place of publication

Praha

Event location

Prague

Event date

Aug 28, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—