One-Pass Complexity of Digital Picture Properties
Stanley M. Selkow · Journal of the ACM · 1972
The computation of a number of picture properties which involve connectivity and component counting is considered.The computational model consists of a one-dimensional array of finite-state automata which scans a digital picture, one row at a time, in one-pass.The inherent complexity of a picture property is reflected in the memory requirements of each element of the corresponding scanner and the number of neighboring automata with which it must communicate.A noncomputable property is presented.