Two-dimensional connected pictures are not recognizable by finite-state acceptors (Q1803862): Difference between revisions

The problem of whether or not the set of connected binary pictures is acceptable by finite-state acceptors has been open for a long time. It was proved by \textit{A. Nakamura} and \textit{A. Rosenfeld} [Three-dimensional connected pictures are not recognizable by finite-state acceptors, Technical Report CAR-TR-566, University of Maryland (1991)] that three- dimensional and connected binary pictures are not recognizable by any deterministic or nondeterministic finite-state array acceptor. But the problem was still left unanswered for the two-dimensional case. The author gives here a solution to this open problem. He proves that the set of two-dimensional connected binary pictures are not recognizable by any deterministic or nondeterministic finite-state acceptor.