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

According to Garey and Johnson (p. 174), REGULAR EXPRESSION NON-UNIVERSALITY is PSPACE-complete. This is the problem of deciding whether a regular expression over $\{0,1\}$ does not generate all strings. So your problem is also PSPACE-complete. Here is one way to see that the OP's problem is in PSPACE. Given a DFA $A$ and a regular expression $r$, construct ...


15

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

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 ...


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^*$ ...


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,...


13

There are different algorithms to convert regular expressions to finite automata. You can go directly from regular expressions to DFAs without building any other automaton first by implicitly doing the subset construction while generating the automaton. Another option to directly obtain deterministic automata is to use the method of derivatives. Checking ...


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

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

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-...


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

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 ...


6

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-...


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 ...


5

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 ...


5

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 ...


4

The following argument is essentially from (1): The decision versions of the two problems are contained in the second level of the polynomial hierarchy (more precisely: in the complexity class $\Sigma^P_2$), as follows. Guess a regular expression of size at most $k$, and check if it is equivalent to the given deterministic finite automaton (respectively: to ...


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/...


3

In addition to domotorp's excellent answer giving $c\le 2$, let me mention that the recent monograph of Jukna (2012) provides an in-depth discussion of this question in Chapter 6.1. According to Jukna, the current best bound is $c \le 1.73$ by Khrapchenko (1978). References Stasys Jukna. Boolean Function Complexity: Advances and Frontiers. Springer, 2012. ...


3

Regular languages are closed under union, concatenation and star, so regular expressions under regular expressions describes regular languages. So, regex, that describe regex, that describe regex still describe family of regular languages, and you can continue that process as long, as you want. Here, by «describe» I mean that first, you have just regex, ...


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

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 ...


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 ...


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 ...


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