12
$\begingroup$

It was shown that any regular language can be specified by planar $\varepsilon$-free nondeterministic finite automaton (Bezáková, Ivona, and Martin Pál. "Planar finite automata."). Is it possible to provide a planar automata intersection algorithm which instantly preserves planarity? Namely, suppose I have two planar automata $M_1$ and $M_2$. Is there exist an algorithm to construct an intersection of $M_1$ and $M_2$ which acts better (in terms of complexity or in terms of the size of the final automaton) than planarization (using results of Ivona and Martin) after the classical intersection? Also, is it possible to define a respective product of automata (and respective product of adjacency matrices)?

$\endgroup$
2
  • 1
    $\begingroup$ Regarding the obvious approach: The (di)graph product in the usual product construction for the intersection of automata is the categorical product. My guess is that this graph product does not preserve planarity... $\endgroup$ Aug 16 '20 at 5:35
  • $\begingroup$ This is just a side question, that I am asking here since you are interested in planar automata: do you know if for an input regular language L, it is decidable whether L has a planar DFA ? I investigated this question a bit and found very few sources, decidability seems difficult and open from what I coud find. $\endgroup$
    – Denis
    Sep 29 at 9:49
7
$\begingroup$

As mentioned in my comment, the usual product construction does not preserve planarity. In fact, there is an intersection of regular languages that can be described by a nonplanar NFA with $n$ states, whereas any equivalent planar NFA needs $\Omega(\frac{n^2}{\log\log n})$ states. The proof is indirect and goes via a lower bound on regular expression size: for two languages $L_1$ and $L_2$, let $L_1 Ш L_2$ denote their shuffle (aka interleaving). Let $L_d = (a_1b_1)^* Ш \ldots Ш (a_db_d)^*$. This language can be expressed as the intersection of the $d$ languages $L_i = (\Sigma\setminus\{a_i,b_i\})^*(a_ib_i)^*(\Sigma\setminus\{a_i,b_i\})^*$. The minimum DFA for $L_d$ is isomorphic to the $d$-dimensional hypercube and has $n=2^d$ states. On the one hand, in (Gruber/Holzer, DLT '09) a lower bound of $2^{\Omega(n/\sqrt{\log\log n})}$ on required regular expression size for $L_d$ is shown. On the other hand, it is proved in (Ellul/Krawetz/Shallit/Wang, JALC '05) that an $s$-state planar NFA can be converted into an equivalent regular expression of size at most $2^{O(\sqrt s)}$. This shows that $s$ must be in $\Omega(\frac{n^2}{\log\log n})$, as desired.

References:

  • Keith Ellul, Bryan Krawetz, Jeffrey O. Shallit, Ming-wei Wang: Regular Expressions: New Results and Open Problems. J. Autom. Lang. Comb. 10(4): 407-437 (2005)
  • Hermann Gruber, Markus Holzer: Tight Bounds on the Descriptional Complexity of Regular Expressions. Developments in Language Theory 2009: 276-287
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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