On the Cell-based Complexity of Recognition of Bounded Configurations by Finite Dynamic Cellular Automata
<|reference_start|>On the Cell-based Complexity of Recognition of Bounded Configurations by Finite Dynamic Cellular Automata: This paper studies complexity of recognition of classes of bounded configurations by a generalization of conventional cellular automata (CA) -- finite dynamic cellular automata (FDCA). Inspired by the CA-based models of biological and computer vision, this study attempts to derive the properties of a complexity measure and of the classes of input configurations that make it beneficial to realize the recognition via a two-layered automaton as compared to a one-layered automaton. A formalized model of an image pattern recognition task is utilized to demonstrate that the derived conditions can be satisfied for a non-empty set of practical problems.<|reference_end|>
@article{makatchev2002on,
    title={On the Cell-based Complexity of Recognition of Bounded Configurations by
  Finite Dynamic Cellular Automata},
    author={Maxim Makatchev},
    journal={arXiv preprint arXiv:cs/0210009},
    year={2002},
    archivePrefix={arXiv},
    eprint={cs/0210009},
    primaryClass={cs.CC cs.CV}
}