On the Cell-based Complexity of Recognition of Bounded Configurations by Finite Dynamic Cellular Automata

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
11 pages, 1 figure

Keywords

Computational Complexity, Computer Vision and Pattern Recognition, F.1.3; F.2.2; F.2.3; I.4.3; I.5.1; I.5.4; I.5.5

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/31311

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0210009
 http://arxiv.org/abs/cs/0210009

Collections

arXiv