13
$\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$
5
  • 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, 2020 at 5:35
  • 1
    $\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, 2021 at 9:49
  • 1
    $\begingroup$ @Denis There is a recent preprint by Bonfante and Deloup (2021): arxiv.org/abs/2109.05735 I did not look into it yet, but I suspect that it contains an affirmative answer to the decidability question. I think I remember that the decidability question was an open problem in Book and Chandra's Seminar paper. Please give an update in case you read it! $\endgroup$ Nov 6, 2021 at 23:30
  • 2
    $\begingroup$ @HermannGruber Thanks, I was not aware of this preprint. After a quick glance I think it is not correct, because they try to use the undirected notion of minor for the directed graphs underlying the DFA. I specifically tried this and was convinced it couldn't work. More precisely I think we can give a counter-example to their theorem 3: contracting a directed edge in a DFA can give a DFA of bigger genus. I'll look more into it before giving a definite answer. $\endgroup$
    – Denis
    Nov 7, 2021 at 9:32
  • 1
    $\begingroup$ @HermannGruber I actually already built an explicit counter-example to this when studying this problem. You can find it on page 7 of this preprint: perso.ens-lyon.fr/denis.kuperberg/papers/MinorsPlanar.pdf This preprint is not available on a repository because I eventually abandoned this line of research, thinking it could not succeed. Also some parts of this preprint are still drafts without proper explanations, and some would need further verification before being shared publicly, I'm sharing it here just for the counter-example. $\endgroup$
    – Denis
    Nov 7, 2021 at 9:51

1 Answer 1

9
$\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\})^*$, for $1\le i \le d$. 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.