Accepting Networks of Evolutionary Picture Processors

• Autorzy: Bottoni P. , Labella A. , Mitrana V.

Identyfikatory

DOI

10.3233/FI-2014-1018

• Języki publikacji: EN

Abstrakty

EN

We extend the study of networks of evolutionary processors accepting words to a similar model, processing rectangular pictures. To this aim, we introduce accepting networks of evolutionary picture processors and investigate their computational power. We show that these networks can accept the complement of any local picture language as well as picture languages that are not recognizable. Some open problems regarding decidability issues and closure properties are finally discussed.

Słowa kluczowe

EN

rectangular picture; local picture language; recognizable picture language; evolutionary picture processor; network of evolutionary picture processors

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 131, nr 3-4
• Strony: 337--349
• Opis fizyczny: Bibliogr. 16 poz., tab.

Twórcy

autor

Bottoni P.

• Department of Computer Science, “Sapienza”, University of Rome, Via Salaria 113, 00198 Rome, Italy

autor

Labella A.

• Department of Computer Science, “Sapienza”, University of Rome, Via Salaria 113, 00198 Rome, Italy

autor

Mitrana V.

• Department of Computer Science, University of Bucharest, Str. Academiei nr. 14, 010014, Bucharest, Romania

Bibliografia

• [1] Csuhaj-Varjú, E., Martın-Vide, C., Mitrana, V.: Hybrid NEPs are computationally complete, Acta Informatica, 41(4-5), 2005, 257–272.
• [2] Giammarresi, D., Restivo, A.: Two-dimensional languages, in [9], 215–267.
• [3] Giammarresi, D., Restivo, A.: Recognizable picture languages, Int. J. Pattern Recognition and Artificial Intelligence, 6, 1992, 241–256.
• [4] Inoue, I., Takanami, I.: A survey of two-dimensional automata theory, in Proc. 5th Int. Meeting of Young Computer Scientists, Lecture Notes in Computer Science 381, 1990, 72–91.
• [5] Margenstern, M., Mitrana, V., Perez-Jimenez, M.: Accepting hybrid networks of evolutionary systems, in DNA Based Computers 10 Lecture Notes in Computer Science 3384, 2005, 235–246.
• [6] Martın-Vide, C., Mitrana, V.: Networks of evolutionary processors: results and perspectives, in Molecular Computational Models: Unconventional Approaches, Idea Group Publishing, Hershey, 2005, 78–114.
• [7] Nivat, M., Saoudi, A., Subramanian, K.G., Siromoney, R., Dare, V.R.: Puzzle grammars and context-free array grammars, Int. J. Pattern Recognition and Artificial Inteligence, 5, 1991, 663–676.
• [8] Rosenfeld, A., Siromoney, R.: Picture languages – a survey, Languages of design, 1, 1993, 229–245.
• [9] Rozenberg, G., Salomaa, A. (eds.), Handbook of Formal Languages, Springer–Verlag, Berlin, vol. I–III, 1997.
• [10] Sankoff, D. et al.: Gene order comparisons for phylogenetic inference:evolution of the mitochondrial genome, Proceedings of the National Academy of Sciences of the United States of America 89, 1992, 6575–6579.
• [11] Siromoney, G., Siromoney, R., Krithivasan, K.: Abstract families of matrices and picture languages, Computer Graphics and Image Processing, 1, 1972, 284–307.
• [12] Siromoney, G., Siromoney, R., Krithivasan, K.: Picture languages with array rewriting rules, Information and Control, 22, 1973, 447–470.
• [13] Subramanian, K.G., Siromoney, R., Dare, V.R., Saoudi, A.: Basic puzzle languages, Int. J. Pattern Recognition and Artificial Intelligence, 9, 1995, 763–775.
• [14] Subramanian, K.G., Siromoney, R.: On array grammars and languages, Cybernetics and Systems, 18, 1987, 77–98.
• [15] Wang, P.S.: Hierarchical structure and complexities of parallel isometric patterns, IEEE Trans. PAM I, 5, 1975, 92–99.
• [16] Wang, P.S.: Sequential/parallel matrix array languages, Journal of Cybernetics, 5, 1975, 19–36