Questions tagged [regular-expressions]

Questions about the theory of regular expressions, both in the sense of Kleene's original definition and of POSIX regular expressions.

62 questions
Filter by
Sorted by
Tagged with
32 views

Publications on left recursion and PCRE regex engine

Is there any paper (or at least technical report / preprint or even thesis) mentioning that regex engines cannot match expressions that contain "left recursion" (explained below)? I am ...
• 11
159 views

Word equations with integer parameters

This is mainly a reference request. Let us define a parameterized expression on a finite alphabet $\Sigma$ as follows: $$e,e':= w\mid w^i \mid e\cdot e'$$ Where $w\in\Sigma^+$ is a word, and $i$ is an ...
• 7,653
37 views

Regex: Pre-determining the position of matching characters

For all regular expressions, is it possible to pre-determine the set of possible positions in which any given sub-expression may be found? If so, is there any existing research on this subject? Here's ...
• 109
157 views

• 121
120 views

Salomaa's axiomatisation of regular languages and the use of regular expression in it

I am reading the classical article of A. Salomaa where he gives two axiom systems for regular sets and proofs consistency and completeness. As I have understood it, an axiomatic system in some logic (...
• 1,947
1 vote
189 views

Hysteresis in finite automata

The concept of hysteresis seems well suited to describe and distinguish finite automata: "Hysteresis is the dependence of the state of a system on its history." (Wikipedia, Hysteresis) "[The ...
668 views

Hierarchies in regular languages

Is there any known "nice" hierarchy $L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots$ (may be finite) inside the class of regular languages $L$? By nice here, the classes in each hierarchy capture ...
• 183
505 views

• 1
949 views

Fully linear time regular expression matching

Is there an $O(n+m)$ algorithm to check whether a size $n$ regular expression matches a size $m$ string, assuming a fixed size alphabet if that matters? The standard NFA algorithm is $O(nm)$ worst ...
• 3,221
3k views

How can one ACTUALLY minimize a regular expression? [closed]

Minimizing regular expressions (in terms of number of symbols) is PSPACE-complete (for example as discussed here: minimizing size of regular expression). But how do you actually do that (i.e., what ...
• 169
207 views

Complexity of DBA-recognizable Omega-Languages

Given an $\omega$-regular expression $r$, how difficult is it to decide if $L(r)$ is recognizable by some deterministic Büchi automaton? I know it is solvable in EXPTIME by converting the regular ...
• 153
331 views

Composition of regular expressions with lookahead into DFAs

Let's say we have a regular expression ("a" | "b"(~!"b"))*, written in Perl or other similar languages that support lookahead, which should match a list of a and b's where b's are not followed by b's. ...
• 366
89 views

Sub optimal regex equivalence

Regex Equivalence is a hard problem which in general takes exponential space and exponential time. Are there any approximation/sub-optimal algorithms with some theoretical guarantees over equivalence ...
• 141
60 views

• 211