Skip to main content
19 votes
Accepted

For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?

This question is addressed in Section 2 of [1], which shows (Theorem 2.6) that the problem is in P if $L(\alpha)$ is finite; coNP-complete if $L(\alpha)$ is infinite but bounded (i.e. $L(\alpha)\...
David's user avatar
  • 308
17 votes
Accepted

Parameterized complexity of inclusion of regular languages

The particular case of language universality (are all words accepted ?) is PSPACE-complete for regular expressions or NFAs. It answers your question: in general the problem stays PSPACE-complete even ...
Denis's user avatar
  • 8,903
16 votes

Hierarchies in regular languages

Here is a list of several hierarchies of interest, some of which were already mentioned in other answers. Concatenation hierarchies A language $L$ is a marked product of $L_0, L_1, \ldots, L_n$ if $...
J.-E. Pin's user avatar
  • 4,841
13 votes
Accepted

Ambiguity of regular expressions

Yes, every regular expression can be converted into an unambiguous one by converting to a DFA and then to a regular expression. And no, there aren't any inherently ambiguous regular languages in the ...
Hermann Gruber's user avatar
12 votes

Hierarchies in regular languages

Expanding the comment: a natural hierarchy is the one induced by the number of states of the DFA. We can define $\mathcal{L}_n = \{ L \mid \text{ exists an n-states DFA D s.t. } L(D) = L \}$ ($D = \{...
Marzio De Biasi's user avatar
9 votes
Accepted

Succinctness of regular expressions with empty word

For a fixed alphabet $\Sigma$, the blow-up is at most polynomial. First, given a regular expression $r$, it is straightforward to construct an expression $\tilde r$ using the operators $a\in\Sigma$, $+...
Emil Jeřábek's user avatar
8 votes

Progress on generalized star-height problem?

This answer is dedicated to the memory of Janusz (John) Antoni Brzozowski, who passed away on October 24, 2019. John is certainly the person who made the star-height problems so famous. Indeed, at a ...
J.-E. Pin's user avatar
  • 4,841
8 votes

Hierarchies in regular languages

I recently came across this paper which may give another relevant example (cf. the last sentence of the abstract): Guillaume Bonfante, Florian Deloup: The genus of regular languages. From the ...
Damiano Mazza's user avatar
7 votes
Accepted

The complexity of conversion from a regular expression to a nondeterminsitic automata and back after changing initial and final states

As observed in the proof of Theorem 6 (later dubbed the "Star Height Lemma") of Gruber/Holzer ICALP 2008, when converting a regular expression into an $\varepsilon$-NFA, then the underlying ...
Hermann Gruber's user avatar
7 votes
Accepted

Kleene Algebra for star-free regular expressions

You might be interested in bounded synchronization delay expressions. See [1] for details on these expressions. To sum up, they are equivalent to star-free expressions, but instead of using complement,...
Denis's user avatar
  • 8,903
7 votes
Accepted

star height of star-free languages

The examples of arbitrary star-height given on the wikipedia page on the star-height problem are star-free: On arbitrary alphabet: :\begin{alignat}{2} e_1 &= a_1^* \\ e_2 &= \left(a_1^*a_2^*...
Denis's user avatar
  • 8,903
7 votes
Accepted

Regular Expressions that converts into unambiguous automata

The paper Ambiguity in Graphs and Expressions (Book et al., 1971) discusses constructing regular expressions that preserve the ambiguity of the input NFA and vice versa. That is, they give a ...
MRC's user avatar
  • 399
7 votes
Accepted

How powerful is POSIX regex

In [1], the authors formally define the notion of an "extended regex" with the intent of capturing the back-reference capability of POSIX/perl/emacs/etc style regexes. Exactly how closely their ...
mhum's user avatar
  • 3,392
5 votes

Hierarchies in regular languages

There are several natural hierarchies for regular languages of infinite words, that convey a notion of "complexity of the language", for instance: Number of ranks needed in a deterministic parity ...
Denis's user avatar
  • 8,903
5 votes

What graphs on $\mathbb{N}$ can be encoded as regular languages?

$\beta(E_1)$ is the language $s^nx,s^{n+1}x$. This language is straightforwardly not regular, by the pumping lemma. If we assume that the language is regular, the pumping lemma tells us that there ...
isaacg's user avatar
  • 806
5 votes
Accepted

Time complexity of derivative-based regex matchers

In Theorem 5.2 of his paper, Brzozowski shows that every regular expression has a finite number of dissimilar derivatives, where two regular expressions $r$ and $r'$ are similar if they are ACU-...
Neel Krishnaswami's user avatar
4 votes
Accepted

Word equations with integer parameters

Here we will show that you can get a Presburger formula from an equation. Let us consider an equation $\alpha = \beta$ over the alphabet $\Sigma$ with the variables $v_\alpha$ in $\alpha$ and $v_\beta$...
Louis's user avatar
  • 775
4 votes
Accepted

Defining regular language classes with disjoint union

Interesting, I was recently writing a blog post on a related topic. Namely, you have probably seen the term rational languages used for regular languages. This is because the generating function (g.f.)...
GBathie's user avatar
  • 296
3 votes

Defining regular language classes with disjoint union

This question has indeed been studied: namely, from the perspective of representing regular languages as unions of so-called regular components that is, loop expressions of the form $uv^+w$, and a ...
Hermann Gruber's user avatar
3 votes
Accepted

Are all RegExp solvable in O(n)?

Thanks to @emil's comment and this stackoverflow answer, I now know that POSIX extended regular expressions are solvable in O(n) but backreferences are at least NP-hard and maybe NP-complete.
Armin's user avatar
  • 223
2 votes
Accepted

Rewrite relations - proof of correctness

To simplify, let $D$ be the domain of $T$ and let $R = \{\epsilon\} \cup (\Sigma^* \setminus \Sigma^*D\Sigma^*)$. Then by definition $$ N(T) = Id_R \quad \text{and} \quad R^{obl}(T) = N(T)(TN(T))^*. $$...
J.-E. Pin's user avatar
  • 4,841
2 votes

Is it useful to "untangle" an NFA by converting to a regular expression and back

In fact, this roundtrip conversion is used in the proof of the Star Height Lemma, and this in turn has lots of implications in the area of descriptional complexity of regular expressions. And here it ...
Hermann Gruber's user avatar
2 votes
Accepted

Are regular expressions polynomially decomposable?

The answer to my question turned out to be positive, which follows from a translation from regular expressions to automata and back. Check the answer of Hermann Gruber to my previous POST.
Bartosz Bednarczyk's user avatar
1 vote
Accepted

Equivalence of regex in Programming language theory

I will give this a go, so that next time somebody is Googling it they can find it 😀. I will try to make this educational and use Haskell, as the question suggests. Let us first define a data type ...
nickie's user avatar
  • 283
1 vote

Match a string agains a set of regexes

Hyperscan is a high-performance multiple regex matching library that uses hybrid automata techniques to allow simultaneous matching of large numbers of regular expressions across streams of data. They ...
Mohemnist's user avatar
  • 230
1 vote

What are regular expressions good for?

Many text markup languages are regular or nearly regular: troff-style markup is regular. I think Markdown would be regular if links were always specified inline (as is required in comments). ...
reinierpost's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible