# Tag Info

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

17

Two more constructions: Brzozowski-McCluskey aka state elimination [1], and Gaussian elimination in a system of equations using Arden's Lemma. The best source on these is probably Jacques Sakarovitch's book [2]. [1] J. Brzozowski, E. McCluskey Jr., Signal ﬂow graph techniques for sequential circuit state diagrams, IEEE Transactions on Electronic Computers ...

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

Kozen's book "Automata & Computability" mentions an elegant generalization of this Floyd-Warshall algorithm. Since you mentioned appealing to algebraists, you might find it useful. You'll find it on page 58-59 of that text. (I think google books has a preview.) Basically, you can define a Kleene algebra on matrices whose entries are from a Kleene ...

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

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 $\... 12 By far the nicest procedure I have seen is the one mentioned by Sylvain. In particular, it seems to yield more concise expressions than others. I wrote this document explaining the method for students last summer. It directly relates to a specific lecture; the reference mentioned is typical definition of regular expressions. A proof of Arden's Lemma is ... 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,... 10 The identity$(x + y)^* = x^*(xy^*)^*$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,... 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 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 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-... 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 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 ... 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 ... 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 ... 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 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, ... 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. ... 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 ... 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