# Tag Info

Accepted

• 4,841
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 ...
• 6,545

• 17.8k

### 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,841

### 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,493
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 ...
• 6,545
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,903
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,903
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 ...
• 399
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,392

### 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,903

### 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 ...
• 806
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.6k
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
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.)...
• 296

### 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 ...
• 6,545
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
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,841

### 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 ...
• 6,545
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.
• 1,337
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 ...
• 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 ...
• 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). ...
• 270

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