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.
Mots-clés : splicing, networks of splicing processors, networks of splicing processors with filtered connections, computational completeness
@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},
pages = {547--572},
publisher = {EDP-Sciences},
volume = {46},
number = {4},
year = {2012},
doi = {10.1051/ita/2012016},
mrnumber = {3107863},
zbl = {1269.68050},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ita/2012016/}
}
TY - JOUR AU - Dassow, Jürgen AU - Manea, Florin AU - Truthe, Bianca TI - Generating Networks of Splicing Processors JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2012 SP - 547 EP - 572 VL - 46 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2012016/ DO - 10.1051/ita/2012016 LA - en ID - ITA_2012__46_4_547_0 ER -
%0 Journal Article %A Dassow, Jürgen %A Manea, Florin %A Truthe, Bianca %T Generating Networks of Splicing Processors %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2012 %P 547-572 %V 46 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2012016/ %R 10.1051/ita/2012016 %G en %F 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) no. 4, pp. 547-572. doi : 10.1051/ita/2012016. http://archive.numdam.org/articles/10.1051/ita/2012016/
[1] , , and , About Universal Hybrid Networks of Evolutionary Processors of Small Size, in Proc. of LATA. Lect. Notes Comput. Sci. 5196 (2008) 28-39. | MR | Zbl
[2] , , and , On the size of computationally complete hybrid networks of evolutionary processors. Theor. Comput. Sci. 410 (2009) 3188-3197. | MR | Zbl
[3] , , and , Solving NP-Complete Problems With Networks of Evolutionary Processors, in Proc. IWANN. Lect. Notes Comput. Sci. 2084 (2001) 621-628. | Zbl
[4] , , and , Networks of evolutionary processors. Acta Inf. 39 (2003) 517-529. | MR | Zbl
[5] , , and , Accepting Networks of Splicing Processors with Filtered Connections, in Proc. of MCU. Lect. Notes Comput. Sci. 4664 (2007) 218-229. | Zbl
[6] and , Networks of Parallel Language Processors, in New Trends in Formal Languages - Control, Cooperation and Combinatorics. Lect. Notes Comput. Sci. 1218 (1997) 299-318. | MR
[7] and , On length-separating test tube systems. Natural Comput. 7 (2008) 167-181. | MR | Zbl
[8] , and , Test tube distributed systems based on splicing. Comput. Artif. Intelligence 15 (1996) 211-232. | MR | Zbl
[9] , and , Networks of evolutionary processors with subregular filters, in Proc. of LATA. Lect. Notes Comput. Sci. 6638 (2011) 262-273. | Zbl
[10] and , On the descriptional complexity of accepting networks of evolutionary processors with filtered connections. Int. J. Found. Comput. Sci. 19 (2008) 1113-1132. | MR | Zbl
[11] , and , Accepting networks of evolutionary processors with filtered connections. J. UCS 13 (2007) 1598-1614. | MR | Zbl
[12] , On accepting networks of splicing processors of size 3, in Proc. CiE. Lect. Notes Comput. Sci. 4497 (2007) 497-506. | MR | Zbl
[13] , and , On small, reduced, and fast universal accepting networks of splicing processors. Theor. Comput. Sci. 410 (2009) 406-416. | MR | Zbl
[14] , and , Accepting Networks of Splicing Processors, in Proc. of CiE. Lect. Notes Comput. Sci. 3526 (2005) 300-309. | Zbl
[15] , and , Accepting networks of splicing processors : complexity results. Theor. Comput. Sci. 371 (2007) 72-82. | MR | Zbl
[16] , and , 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
[17] , and , Accepting Hybrid Networks of Evolutionary Processors, in Proc. of DNA. Lect. Notes Comput. Sci. 3384 (2004) 235-246. | Zbl
[18] and , Networks of evolutionary processors : Results and perspectives, in Molecular Computational Models : Unconventional Approaches (2005) 78-114. | Zbl
[19] , and , DNA computing - new computing paradigms. Texts in Theor. Comput. Sci. Springer (1998). | MR | Zbl
[20] and , Handbook of Formal Languages. Springer-Verlag, New York, Inc., Secaucus, NJ, USA (1997). | Zbl
Cité par Sources :
