A Denotational Semantics for Synchronized Regular Expressions (extended version)
2026-08-18 • Formal Languages and Automata Theory
Formal Languages and Automata Theory
AI summaryⓘ
The authors study an extension of regular expressions called pure and full synchronized regular expressions, which add labels to certain operators to force them to behave in sync. They show that common regex features like backreferences can be translated into these synchronized forms. They introduce a new way to understand these expressions using denotational semantics rather than previous operational approaches. The authors prove some important properties about the languages defined by these expressions, including their closure under some operations and the complexity of matching words. They also discuss how these languages relate to other language models.
regular expressionsbackreferencesKleene staralternationdenotational semanticsoperational semanticsNP-completelanguage closure propertiespumping lemmasynchronization
Authors
Lukas Grätz
Abstract
Pure and full synchronized regular expressions (pure sregex and full sregex ) extend regular expressions by adding labels to the operators (Kleene star and alternation). Operators within the same scope are synchronized if they have the same label. We show that a regular expression with backreferences (known from practical regex engines) can be translated into a full sregex. Previous work did not consider synchronized alternations or nested star synchronization. Within the same scope, stars with the same label match the same number of iterations, alternations with the same label match the same choice. The scope may depend on the current iteration of an outer star. Pure sregexes restrict synchronization to the local scope, while full sregexes also allow synchronization across iterations. In contrast to operational semantics in previous work on backreferences, we present a denotational semantics, where concretizations act similarly to valuations in logic. As with backreferences, we show that matching a word is NP-complete. Pure and full synchronized languages are considered and we show that they are closed under concatenation, union and star. By a pumping lemma, they are not closed under intersection. Relationships to other language models are discussed.