<p>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 <span class="math-container">$n$</span> states, whereas <em>any</em> equivalent planar NFA needs <span class="math-container">$\Omega(\frac{n^2}{\log\log n})$</span> states. The proof is indirect and goes via a lower bound on regular expression size: for two languages <span class="math-container">$L_1$</span> and <span class="math-container">$L_2$</span>, let <span class="math-container">$L_1 Ш L_2$</span> denote their <a href="https://en.wikipedia.org/wiki/Shuffle_algebra" rel="nofollow noreferrer">shuffle</a> (aka interleaving). Let <span class="math-container">$L_d = (a_1b_1)^* Ш \ldots Ш  (a_db_d)^*$</span>. This language can be expressed as the intersection of the <span class="math-container">$d$</span> languages <span class="math-container">$L_i = (\Sigma\setminus\{a_i,b_i\})^*(a_ib_i)^*(\Sigma\setminus\{a_i,b_i\})^*$</span>, for <span class="math-container">$1\le i \le d$</span>. The minimum DFA for <span class="math-container">$L_d$</span> is isomorphic to the <span class="math-container">$d$</span>-dimensional hypercube and has <span class="math-container">$n=2^d$</span> states. On the one hand, in (Gruber/Holzer, DLT '09) a lower bound of <span class="math-container">$2^{\Omega(n/\sqrt{\log\log n})}$</span> on required regular expression size for <span class="math-container">$L_d$</span> is shown. On the other hand, it is proved in (Ellul/Krawetz/Shallit/Wang, JALC '05) that an <span class="math-container">$s$</span>-state planar  NFA can be converted into an equivalent regular expression of size at most <span class="math-container">$2^{O(\sqrt s)}$</span>. This shows that <span class="math-container">$s$</span> must be in <span class="math-container">$\Omega(\frac{n^2}{\log\log n})$</span>, as desired.</p>
<p>References:</p>
<ul>
<li>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)</li>
<li>Hermann Gruber, Markus Holzer: Tight Bounds on the Descriptional Complexity of Regular Expressions. Developments in Language Theory 2009: 276-287</li>
</ul>

CC BY-SA 4.0
2020-08-20T10:44:36.127Z
2021-11-07T08:50:53.483Z
2021-11-07T08:50:53.483Z
Hermann Gruber
<p>It was shown that any regular language can be specified by planar <span class="math-container">$\varepsilon$</span>-free nondeterministic finite automaton (<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.1550" rel="noreferrer">Bezáková, Ivona, and Martin Pál. &quot;Planar finite automata.&quot;</a>). Is it possible to provide a planar automata intersection algorithm which instantly preserves planarity? Namely, suppose I have two planar automata <span class="math-container">$M_1$</span> and <span class="math-container">$M_2$</span>. Is there exist an algorithm to construct an intersection of <span class="math-container">$M_1$</span> and <span class="math-container">$M_2$</span> 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)?</p>

CC BY-SA 4.0
2020-08-16T05:35:46.810Z
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...
Hermann Gruber
CC BY-SA 4.0
2021-09-29T09:49:26.060Z
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.
Denis
CC BY-SA 4.0
2021-11-06T23:30:48.613Z
@Denis There is a recent preprint by Bonfante and Deloup (2021): https://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!
Hermann Gruber
CC BY-SA 4.0
2021-11-07T09:32:41.007Z
@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.
Denis
CC BY-SA 4.0
2021-11-07T09:51:00.077Z
@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: https://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.
Denis
<fl.formal-languages><automata-theory><regular-language><planar-graphs>
Planarity of planar finite automata intersection
gsv
# Planarity of planar finite automata intersection

(Asked by: username_0 on 2020-08-15)

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."](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.1550)). 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)?

**Tags:** fl.formal-languages, automata-theory, regular-language, planar-graphs

> **Comments:**
> **username_1**: 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...  
> **username_2**: 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.  
> **username_1**: @username_2 There is a recent preprint by Bonfante and Deloup (2021): https://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!  
> **username_2**: @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.  
> **username_2**: @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: https://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.  

---

## 1 answers

### Answer by username_1 on 2020-08-20. Score: 9

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](https://en.wikipedia.org/wiki/Shuffle_algebra) (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)
* username_1, Markus Holzer: Tight Bounds on the Descriptional Complexity of Regular Expressions. Developments in Language Theory 2009: 276-287


---

