17

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)\subseteq w_1^*w_2^*\ldots w_k^*$ for some $w_1,\ldots, w_k$); PSPACE-complete otherwise. [1] Harry B. Hunt, Daniel J. Rosenkrantz, Thomas G. Szymanski, On the ...


16

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 $L = L_0a_1L_1 \cdots a_nL_n$ for some letters $a_1, \ldots, a_n$. Concatenation hierarchies are defined by alternating Boolean operations and polynomial ...


14

Let $A = \{1, ..., k\}$ be an ordered alphabet. Then each word on $A^*$ can be viewed as a number in base $k + 1$ (note that $0$ is never used on purpose). Now define $$ rank(u) = \begin{cases} u &\text{if $u \in L$} \\ 0 &\text{otherwise} \end{cases} $$ Then $rank$ preserves the shortlex (or radix) order, which is the order $\leqslant$ on $A^*$ ...


14

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 for fixed $E_1$, since language universality corresponds to $E_1=\Sigma^*$. It is indeed hard to find a modern readable PSPACE-hardness proof for regular ...


13

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 sense described in the question. This is a classic result in automata theory:  R. Book, S. Even, S. Greibach and G. Ott, Ambiguity in graphs and expressions, ...


13

The identity $(x + y)^* = x^*(yx^*)^*$ is a classical identity of regular expressions, but it is a nontrivial problem to find a complete set of identities for regular expressions. An infinite complete set was proposed by John Conway and this conjecture was ultimately proved by D. Krob. J.H. Conway, Regular algebra and finite machines, Chapman and Hall, 1971,...


12

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 = \{Q, \Sigma, \delta, q_0, F \}$, $|Q| = n$ ) Clearly $\mathcal{L}_n \subseteq \mathcal{L}_{n+1}$ (simply use dead states) To show the proper inclusion $\...


10

From your example, it is easy to derive a language $L$, such that neither $L$ nor its complement is recognized by a DBA. Take an alphabet of four letter $\{a,b,c,d\}$, and let $L=((a+b)^* a^\omega)+(c^*d)^\omega$. It is not DBA-recognizable because of the $\{a,b\}$-part, and its complement is not because of the $\{c,d\}$-part. For a less artificial example,...


8

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 abstract: The article defines and studies the genus of finite state deterministic automata (FSA) and regular languages. Indeed, a FSA can be seen as a graph for which ...


7

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 definition matches the exact POSIX specification is an exercise left to the reader. Under their definition, extended regexes are a proper subset of Type 1 (context-...


7

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, they restrict the use of the Kleene star to certain languages: the prefix codes with bounded synchronization delay. This way, you can have your ...


7

This is another classical example of inductive enumeration. I assume that we are given some DFA for the language $L$ over an ordered alphabet $\Sigma$. Let's start with the easier case of words of length $n$. Using linear algebra, given a prefix $w$, we can compute efficiently $N(w,m) = |\{ x \in \Sigma^m : wx \in L\}|$. Define $N(m) = N(\epsilon,m)$ for ...


7

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 conference in Santa Barbara in December 1979, he presented a selection of six open problems about regular languages and mentioned two other topics in the ...


7

To add to Yuval's answer, and provide references: If you want more references regarding the complexity of ranking different classes of sets, here are some places to look: A. Goldberg and M. Sipser, Compression and ranking. SIAM J. Comput. 20 (1991), 524-536. L. Hemachandra and S. Rudich, On the complexity of ranking. J. Comput. System Sci. 41 (1990), 251-...


6

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-02927-1_16 (preprint). For a fixed size alphabet, Sebastian Maneth pointed out to me that $O(n+m)$ is possible for deterministic regular expressions by ...


6

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: Given a regular expression r of alphabetic width n, i.e. with n alphabetic letters, you can enumerate all regular expressions of alphabetic width 1,2,3, one by ...


5

$\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 must exist some $p, q$ such that for all $n \ge p$, $s^{n+q}x,s^{n+1}x$ is also in the language. This is false, meaning that the language is not regular. A similar ...


5

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 automaton Wadge (or Wagner) hierarchy: topological complexity, $\omega^\omega$ levels. These hierarchies can be generalised for regular languages of infinite ...


4

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-equivalent at the outermost level. That is, consider the equivalence relation generated by the following equivalences: $$ \array{ r \vee r & \equiv & r \\ r ...


3

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.


3

For tree automata, you have the Mostowski hierarchy, which is about the complexity of acceptance condition: each level is of the form $(i,j)$ with $i\in\{0,1\}$ and $i\leq j$. Being at level $(i,j)$ means that there is a parity automaton using parities from $i$ to $j$ recognizing the language. For more on parity condition, see here: https://en.wikipedia.org/...


2

The solution of the restricted star-height problem inspired the rich theory of regular cost functions (by Colcombet), which in turn helped to solve other decidability problems and offers new tools to attack open problems. This theory is still developing and was extended to infinite words, finite trees, infinite trees, with its own set of deep results and ...


2

The problem you are trying to solve is called PARTIAL-MATCH: given a database of sets, and a query set, find all sets in the database that contain the query. The most relevant paper is one by Charikar, Indyk and Panigrahy from ICALP 2002: New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems That's on the ...


2

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))^*. $$ Here is a formal way to justify your idea. Let $(u,v) \in \Sigma^* \times \Sigma^*$. By definition, $(u,v) \in R^{obl}(T)$ if and only if $(u,v)$ can be ...


1

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 explained their approach here: https://www.hyperscan.io/2015/10/20/match-regular-expressions Apparently, they didn't find a fast algorithm (in the worst case) ...


1

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 question whether you want the strings in $L$ to be validly parenthesized. One way I an interpret your question is that you want the strings of your language to be ...


1

If you are planning on using this kind of syntax for a real application requiring a parser, you probably do not want to wander outside the polynomial realm. So you might be interested by linear context-fre rewriting systems which is a hierarchy of grammatical formalisms parsable in polynomial time. This has been heavily explored by the community that ...


1

The Mostowski hierarchy is about parity automata, thus infinite trees. I believe, it is beyond the question. Best work I can think of about automata on finite trees is TATA http://tata.gforge.inria.fr/ . But it is mostly about finite state ones, and rather concerned about using them as a framework for satisfiability problems. Few years ago, during my ...


1

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). Wikipedia markup was regular for a while and still is for the most part. HTML is mostly regular. The subset of HTML in which no element may be directly nested or ...


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