Two-dimensional connected pictures are not recognizable by finite-state acceptors (Q1803862): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0020-0255(93)90039-o / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W4231225572 / rank | |||
Normal rank |
Latest revision as of 10:36, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Two-dimensional connected pictures are not recognizable by finite-state acceptors |
scientific article |
Statements
Two-dimensional connected pictures are not recognizable by finite-state acceptors (English)
0 references
29 June 1993
0 references
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.
0 references
finite-state acceptors
0 references
connected binary pictures
0 references