10
$\begingroup$

Suppose that a regular expression $\mathcal{R}$ over an alphabet $\Sigma$ is given. It is well-known that one can now construct a non-deterministic finite automaton $\mathcal{A}$ such that $\mathcal{R}$ and $\mathcal{A}$ recognize the same languages. Let $\mathcal{A}_{q,q'}$ be an automaton obtained from $\mathcal{A}$ by changing its initial state to $q$ and its final state to $q'$ (where $q, q'$ are from the state-space of $\mathcal{A}$). My question is:

Is this the case for every regular expression $\mathcal{R}$ that there exists an equivalent NFA $\mathcal{A}$ of size polynomial w.r.t $\mathcal{R}$ such that for all pairs of states $(q,q')$ the automata $\mathcal{A}_{q,q'}$ have equivalent regular expressions $\mathcal{R}_{q,q'}$ of size polynomial w.r.t $\mathcal{R}$?

I'm aware that generally, a regular expression may be of size exponential w.r.t. the input automaton. However, in this case, such an automaton comes from another regular expression; thus, it is unclear to me what the answer should be. To clarify: I use the standard definition of regular expressions from Sipser's book so the syntax of regular expressions is as follows:

$ \mathcal{R} ::= a \in \Sigma \mid \varepsilon \mid \emptyset \mid \mathcal{R} \cup \mathcal{R} \mid \mathcal{R} \circ \mathcal{R} \mid \mathcal{R}^*. $

In particular, extra features such as complementation and intersection are not allowed.
$\endgroup$
5
  • 1
    $\begingroup$ Observation that may be helpful identifying edge cases. I think the following holds: let $R$ be a regular expression with $*$-depth $k$ and $A$ the automaton constructed from $R$ via Thompson's construction. Then for every $q_1,q_2$ in $A$, there exists a regular expression $R[q_1,q_2]$ matching $A_{q_1,q_2}$ of size at most $3^k|R|$. This is an induction on $R$. The only "challenging" case is when $R=S^*$, with $R[q_1,q_2] = S[q_1,q_f] (S[q_0,q_f])^* S[q_f, q_2]$ where $q_0,q_f$ are the initial/final state of $S$. It triples the size of the regexp. For bounded depth of $*$, that should work. $\endgroup$
    – holf
    Dec 18, 2023 at 14:35
  • $\begingroup$ Unfortunately in my case the star depth can be unbounded. So do you think that the answer to my question is probably negative? $\endgroup$ Dec 18, 2023 at 15:36
  • 1
    $\begingroup$ No idea, just trying to identify where the naive approach breaks ;)! $\endgroup$
    – holf
    Dec 19, 2023 at 14:35
  • 2
    $\begingroup$ I think the focus should be on the follow-up question, because if you put no constraint on how A is produced, you can always put in A complicated parts that recognize the same language but will induce exponential expressions. It is for instance trivial when A is not required to be pruned, then you can just add an unreachable part A' next to it. $\endgroup$
    – Denis
    Dec 19, 2023 at 18:38
  • $\begingroup$ Dear Denis, you are of course right! Thanks a lot for your observation. I've just updated my post to fully focus on the follow-up question. $\endgroup$ Dec 19, 2023 at 19:58

1 Answer 1

7
+400
$\begingroup$

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 graph has treewidth at most $2$. This implies that the graph has undirected cycle rank at most $2\log n$ by Corollary 3.1 in Gruber JoC 2012. (Undirected cycle rank soon thereafter became better known as tree-depth.) In Gruber/Holzer IJFCS 2013, the problem of converting an $n$-state NFA into a regular expression is studied as a parameterized problem; we can convert an $n$-state $\varepsilon$-NFA of undirected cycle rank $k$ into an equivalent regular expression of size $|\Sigma|\cdot 4^k \cdot n$ (Theorem 9).

Putting it together, we obtain a bound of $|\Sigma|\cdot 4^{2 \log n} \cdot n = |\Sigma| \cdot n^5$, which is polynomial in $n$ as desired.

I assume that the bound will not be reached in the worst case.

References:

  • Hermann Gruber and Markus Holzer. Finite Automata, Digraph Connectivity, and Regular Expression Size. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Reykjavik, Iceland, volume 5126 of Lecture Notes in Computer Science, pages 39-50. Springer, July 2008.
  • Hermann Gruber. On Balanced Separators, Treewidth, and Cycle Rank. Journal of Combinatorics, 3(4):669-682, 2012.
  • Hermann Gruber and Markus Holzer. Provably Shorter Regular Expressions From Finite Automata. International Journal of Foundations of Computer Science, 24(8):1255-1279, 2013.
$\endgroup$
2
  • 1
    $\begingroup$ Many thanks for the answer. This result is amazing! Could you please tell me whether the bound holds is we assume that the desired automaton is free of epsilon-transitions? $\endgroup$ Dec 22, 2023 at 13:33
  • 2
    $\begingroup$ Bartosz, the series parallel structure of the Thompson construction seems essential for the treewidth 2 argument. I am pretty sure that no analogous results are known for e-free NFAs. $\endgroup$ Dec 22, 2023 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.