Publication
Acta Informatica
Paper

Inherently nonplanar automata

View publication

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.

Date

Publication

Acta Informatica

Authors

Share