Generating Networks of Splicing Processors
Dassow, Jürgen ; Manea, Florin ; Truthe, Bianca
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012), p. 547-572 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

In this paper, we introduce generating networks of splicing processors (GNSP for short), a formal languages generating model related to networks of evolutionary processors and to accepting networks of splicing processors. We show that all recursively enumerable languages can be generated by GNSPs with only nine processors. We also show, by direct simulation, that two other variants of this computing model, where the communication between processors is conducted in different ways, have the same computational power.

Publié le : 2012-01-01
DOI : https://doi.org/10.1051/ita/2012016
Classification:  68Q05,  68Q42,  68Q45 
@article{ITA_2012__46_4_547_0,
     author = {Dassow, J\"urgen and Manea, Florin and Truthe, Bianca},
     title = {Generating Networks of Splicing Processors},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {46},
     year = {2012},
     pages = {547-572},
     doi = {10.1051/ita/2012016},
     mrnumber = {3107863},
     zbl = {1269.68050},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2012__46_4_547_0}
}

Dassow, Jürgen; Manea, Florin; Truthe, Bianca. Generating Networks of Splicing Processors. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) pp. 547-572. doi : 10.1051/ita/2012016. http://gdmltest.u-ga.fr/item/ITA_2012__46_4_547_0/

[1] A. Alhazov, E. Csuhaj-Varjú, C. Martín-Vide and Y. Rogozhin, About Universal Hybrid Networks of Evolutionary Processors of Small Size, in Proc. of LATA. Lect. Notes Comput. Sci. 5196 (2008) 28-39. | MR 2540310 | Zbl 1156.68379

[2] A. Alhazov, E. Csuhaj-Varjú, C. Martín-Vide and Y. Rogozhin, On the size of computationally complete hybrid networks of evolutionary processors. Theor. Comput. Sci. 410 (2009) 3188-3197. | MR 2546875 | Zbl 1173.68019

[3] J. Castellanos, C. Martin-Vide, V. Mitrana and J.M. Sempere, Solving NP-Complete Problems With Networks of Evolutionary Processors, in Proc. IWANN. Lect. Notes Comput. Sci. 2084 (2001) 621-628. | Zbl 0982.68767

[4] J. Castellanos, C. Martín-Vide, V. Mitrana and J.M. Sempere, Networks of evolutionary processors. Acta Inf. 39 (2003) 517-529. | MR 1993630 | Zbl 1060.68046

[5] J. Castellanos, F. Manea, L.F. De Mingo López and V. Mitrana, Accepting Networks of Splicing Processors with Filtered Connections, in Proc. of MCU. Lect. Notes Comput. Sci. 4664 (2007) 218-229. | Zbl 1211.68199

[6] E. Csuhaj-Varjú and A. Salomaa, Networks of Parallel Language Processors, in New Trends in Formal Languages - Control, Cooperation and Combinatorics. Lect. Notes Comput. Sci. 1218 (1997) 299-318. | MR 1605238

[7] E. Csuhaj-Varjú and S. Verlan, On length-separating test tube systems. Natural Comput. 7 (2008) 167-181. | MR 2403209 | Zbl 1146.68372

[8] E. Csuhaj-Varjú, L. Kari and G. Paun, Test tube distributed systems based on splicing. Comput. Artif. Intelligence 15 (1996) 211-232. | MR 1405413 | Zbl 0852.68051

[9] J. Dassow, F. Manea and B. Truthe, Networks of evolutionary processors with subregular filters, in Proc. of LATA. Lect. Notes Comput. Sci. 6638 (2011) 262-273. | Zbl 1230.68125

[10] C. Drăgoi and F. Manea, On the descriptional complexity of accepting networks of evolutionary processors with filtered connections. Int. J. Found. Comput. Sci. 19 (2008) 1113-1132. | MR 2454740 | Zbl 1175.68161

[11] C. Drăgoi, F. Manea and V. Mitrana, Accepting networks of evolutionary processors with filtered connections. J. UCS 13 (2007) 1598-1614. | MR 2390239 | Zbl 1175.68160

[12] R. Loos, On accepting networks of splicing processors of size 3, in Proc. CiE. Lect. Notes Comput. Sci. 4497 (2007) 497-506. | MR 2646261 | Zbl 1151.68418

[13] R. Loos, F. Manea and V. Mitrana, On small, reduced, and fast universal accepting networks of splicing processors. Theor. Comput. Sci. 410 (2009) 406-416. | MR 2493988 | Zbl 1160.68014

[14] F. Manea, C. Martín-Vide and V. Mitrana, Accepting Networks of Splicing Processors, in Proc. of CiE. Lect. Notes Comput. Sci. 3526 (2005) 300-309. | Zbl 1113.68401

[15] F. Manea, C. Martín-Vide and V. Mitrana, Accepting networks of splicing processors : complexity results. Theor. Comput. Sci. 371 (2007) 72-82. | MR 2298667 | Zbl 1108.68052

[16] F. Manea, C. Martín-Vide and V. Mitrana, Accepting networks of evolutionary word and picture processors : A survey, in Scientific Applications of Language Methods, edited by Carlos Martín-Vide. Mathematics, Computing, Language, and Life : Frontiers in Mathematical Linguistics and Language Theory 2 (2010) 525-560. | Zbl 1230.68072

[17] M. Margenstern, V. Mitrana and M.J. Pérez-Jiménez, Accepting Hybrid Networks of Evolutionary Processors, in Proc. of DNA. Lect. Notes Comput. Sci. 3384 (2004) 235-246. | Zbl 1116.68463

[18] C. Martín-Vide and V. Mitrana, Networks of evolutionary processors : Results and perspectives, in Molecular Computational Models : Unconventional Approaches (2005) 78-114. | Zbl 1060.68046

[19] G. Paun, G. Rozenberg and A. Salomaa, DNA computing - new computing paradigms. Texts in Theor. Comput. Sci. Springer (1998). | MR 1724525 | Zbl 1069.68559

[20] G. Rozenberg and A. Salomaa, Handbook of Formal Languages. Springer-Verlag, New York, Inc., Secaucus, NJ, USA (1997). | Zbl 0866.68057