Ashok K. Chandra, Prabhakar Raghavan, et al.
Computational Complexity
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, D.S. Hirschberg, et al.
Theoretical Computer Science
Conference paper
Structure and complexity of relational queries
Ashok K. Chandra, David Harel
FOCS 1980