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)\...
- 308
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
$...
- 4,761
14
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 ...
- 8,473
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 ...
- 5,649
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 = \{...
- 22.5k
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$, $+...
- 15.6k
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 ...
- 5,233
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^*...
- 8,473
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 ...
- 389
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 ...
- 3,382
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,...
- 8,473
7
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 ...
- 4,761
6
votes
Accepted
Fully linear time regular expression matching
Groz et al. explicitly state that the best known algorithm for general regular expressions (as of 2012) is $O(nm(\log\log n)/(\log n)^{3/2}+n+m)$, due to Bille and Thorup 2009, doi:10.1007/978-3-642-...
- 18.9k
6
votes
Accepted
How can one ACTUALLY minimize a regular expression?
Finding the answer to your question is not overly difficult, if one is used to proving PSPACE upper bounds. But I think one cannot find an answer to your question in the literature, so here it is:
...
- 5,649
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 ...
- 8,473
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-...
- 32.2k
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 ...
- 752
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$...
- 775
4
votes
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.)...
- 281
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.
- 223
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 ...
- 5,649
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))^*.
$$...
- 4,761
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 ...
- 230
1
vote
Writing a regular expression for character set $\Sigma = \{a,b,(,)\}$ that not have a parenthesis inside a parenthesis
First of all, in order to avoid confusion with the parenthesis found in a regular expression, I will use the characters $[$ and $]$ instead of parenthesis in my strings.
I can't tell from the ...
- 2,758
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).
...
- 270
Only top scored, non community-wiki answers of a minimum length are eligible