Cover Image

On the Expressive Power of Regular Expressions with Backreferences

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nogami, Taisei, Terauchi, Tachio
Format:	Preprint
Published:	2023
Subjects:	Formal Languages and Automata Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Regular Expressions with Backreferences on Multiple Context-Free Languages, and the Closed-Star Condition
by: Nogami, Taisei, et al.
Published: (2024)

Efficient Matching of Some Fundamental Regular Expressions with Backreferences
by: Nogami, Taisei, et al.
Published: (2025)

Hardness of Regular Expression Matching with Extensions
by: Nogami, Taisei, et al.
Published: (2026)

Regular Expression Denial of Service Induced by Backreferences
by: Liu, Yichen, et al.
Published: (2026)

Regular Expressions with Backreferences and Lookaheads Capture NLOG
by: Uezato, Yuya
Published: (2024)

On Decidability and Expressive Power of Fusion Grammars
by: Pshenitsyn, Tikhon
Published: (2023)

Weighted Automata and Regular Expressions for Financial Systems
by: Droste, Manfred, et al.
Published: (2026)

Well-Behaved (Co)algebraic Semantics of Regular Expressions in Dafny
by: Zetzsche, Stefan, et al.
Published: (2024)

GrappaRE -- A Tool for Efficient Graph Recognition Based on Finite Automata and Regular Expressions
by: De Rosa, Mattia, et al.
Published: (2025)

The Complexity of Aggregates over Extractions by Regular Expressions
by: Doleschal, Johannes, et al.
Published: (2020)

Linear Matching of JavaScript Regular Expressions
by: Barrière, Aurèle, et al.
Published: (2023)

Towards Efficient Matching of Regexes with Backreferences using Register Set Automata (Technical Report)
by: Havlena, Vojtěch, et al.
Published: (2022)

On Synthesis of Timed Regular Expressions
by: Wang, Ziran, et al.
Published: (2025)

Computational Model for Parsing Expression Grammars
by: Rubtsov, Alexander, et al.
Published: (2024)

Regular Languages in the Sliding Window Model
by: Ganardi, Moses, et al.
Published: (2024)

Shuffles of Context-Free Languages along Regular Trajectories
by: Barloy, Corentin, et al.
Published: (2026)

Regular Grammars for Sets of Graphs of Tree-Width 2
by: Bozga, Marius, et al.
Published: (2024)

$ω$-regular Expression Synthesis from Transition-Based Büchi Automata
by: Pert, Charles, et al.
Published: (2024)

Constructing Concise Characteristic Samples for Acceptors of Omega Regular Languages
by: Angluin, Dana, et al.
Published: (2022)

A Regular and Complete Notion of Delay for Streaming String Transducers
by: Filiot, Emmanuel, et al.
Published: (2022)

On the Complexity of Computing the Co-lexicographic Width of a Regular Language
by: Becker, Ruben, et al.
Published: (2024)

The Power-Set Construction for Tree Algebras
by: Blumensath, Achim
Published: (2022)

Backward Responsibility in Transition Systems Using General Power Indices
by: Baier, Christel, et al.
Published: (2024)

A Completeness Theorem for Probabilistic Regular Expressions
by: Różowski, Wojciech, et al.
Published: (2023)

Correct and Optimal: the Regular Expression Inference Challenge
by: Valizadeh, Mojtaba, et al.
Published: (2023)

The Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective
by: Bergsträßer, Pascal, et al.
Published: (2024)

On The Space Complexity of Partial Derivatives of Regular Expressions with Shuffle
by: Ancona, Davide, et al.
Published: (2025)

Exact Expressive Power of Transformers with Padding
by: Merrill, William, et al.
Published: (2025)

A Complete Propositional Dynamic Logic for Regular Expressions with Lookahead
by: Nakamura, Yoshiki
Published: (2026)

Directed Regular and Context-Free Languages
by: Ganardi, Moses, et al.
Published: (2024)

Regular Expressions with Backreferences: Polynomial-Time Matching Techniques
by: Schmid, Markus L.
Published: (2019)

Regular language quantum states
by: Florido-Llinàs, Marta, et al.
Published: (2024)

An Algebraic View of the Expressivity of Recurrent Language Models
by: Nowak, Franz, et al.
Published: (2026)

Compiling Quantum Regular Language States
by: Bellante, Armando, et al.
Published: (2026)

Image Reflection on Process Graphs -- A Novel Approach for the Completeness of an Axiomatization of 1-Free Regular Expressions Modulo Bisimilarity
by: Zhang, Yuanrui, et al.
Published: (2023)

Decoupled Planning for Multiple Omega-Regular Objectives
by: Avni, Guy, et al.
Published: (2026)

The Expansion Problem for Infinite Trees
by: Blumensath, Achim
Published: (2023)

Mata, a Fast and Simple Finite Automata Library (Technical Report)
by: Chocholatý, David, et al.
Published: (2023)

Simulation Limitations of Affine Cellular Automata
by: Hudcová, Barbora, et al.
Published: (2023)

Safety and Liveness of Quantitative Properties and Automata
by: Boker, Udi, et al.
Published: (2023)