Linear-time recognition of connectivity of binary images on 1-bit inter-cell communication cellular automaton (Q5940983): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/s0167-8191(00)00079-x / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2054226733 / rank | |||
Normal rank | |||
| links / mardi / name | links / mardi / name | ||
Latest revision as of 10:47, 30 July 2024
scientific article; zbMATH DE number 1635138
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Linear-time recognition of connectivity of binary images on 1-bit inter-cell communication cellular automaton |
scientific article; zbMATH DE number 1635138 |
Statements
Linear-time recognition of connectivity of binary images on 1-bit inter-cell communication cellular automaton (English)
0 references
20 August 2001
0 references
We introduce a new class of two-dimensional Cellular Automata (CAs) whose inter-cell communication is restricted to 1-bit and propose a linear-time connectivity recognition algorithm for two-dimensional binary images. Precisely, it is shown that a set of two-dimensional connected binary images of size \(m\times\)n can be recognized in \(2(m+n)+O(1)\) steps by a two-dimensional CA with 1-bit inter-cell communication.
0 references
two-dimensional cellular automata
0 references
