Ashok K. Chandra, George Markowsky
Discrete Mathematics
Paper
Inherently nonplanar automata
Abstract
It is shown that for every finite-state automaton there exists an equivalent nondeterministic automaton with a planar state graph. However there exist finite-state automata with no equivalent deterministic automaton with a planar state graph. © 1976 Springer-Verlag.
Related
Manuel Blum, Ashok K. Chandra, et al.
Information Processing Letters
Ashok K. Chandra, Martin Tompa
Discrete Applied Mathematics
Ashok K. Chandra, Prabhakar Raghavan, et al.
Computational Complexity