Advances in Regular Expression Matching and Automata Theory

The field of regular expression matching and automata theory is experiencing significant developments, with a focus on improving efficiency and generality. Researchers are exploring new techniques to enhance matching algorithms, including the use of automata theory and stringology. A key area of interest is the study of regular languages, including their properties and applications. Notably, the concept of Wheeler languages is being extended to Universally Wheeler languages, which have implications for data indexing and language theory. Additionally, there is a growing interest in the minimization of automata, particularly in the context of polynomial-time minimizable omega-automata.

Some noteworthy papers in this area include: The Efficient Matching of Some Fundamental Regular Expressions with Backreferences paper, which presents a quadratic-time matching algorithm for a specific class of regular expressions with backreferences. The Universally Wheeler Languages paper, which introduces a new class of regular languages that are Wheeler with respect to all orders of a given alphabet and explores their properties and applications.

Sources

Efficient Matching of Some Fundamental Regular Expressions with Backreferences

The Trichotomy of Regular Property Testing

Universally Wheeler Languages

On closure properties of TotP

Characterizing the Polynomial-Time Minimizable $\omega$-Automata

From regular expressions to deterministic finite automata: $2^{\frac{n}{2}+\sqrt{n}(\log n)^{\Theta(1)}}$ states are necessary and sufficient

Built with on top of