Generating Networks of Splicing Processors

Jürgen Dassow; Florin Manea; Bianca Truthe

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2012)

  • Volume: 46, Issue: 4, page 547-572
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Dassow, Jürgen, Manea, Florin, and Truthe, Bianca. "Generating Networks of Splicing Processors." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 46.4 (2012): 547-572. <http://eudml.org/doc/273047>.

@article{Dassow2012,
abstract = {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.},
author = {Dassow, Jürgen, Manea, Florin, Truthe, Bianca},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {splicing; networks of splicing processors; networks of splicing processors with filtered connections; computational completeness; networks of splicing processors with filters},
language = {eng},
number = {4},
pages = {547-572},
publisher = {EDP-Sciences},
title = {Generating Networks of Splicing Processors},
url = {http://eudml.org/doc/273047},
volume = {46},
year = {2012},
}

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
PB - EDP-Sciences
VL - 46
IS - 4
SP - 547
EP - 572
AB - 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.
LA - eng
KW - splicing; networks of splicing processors; networks of splicing processors with filtered connections; computational completeness; networks of splicing processors with filters
UR - http://eudml.org/doc/273047
ER -

References

top
  1. [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. Zbl1156.68379MR2540310
  2. [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. Zbl1173.68019MR2546875
  3. [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. Zbl0982.68767
  4. [4] J. Castellanos, C. Martín-Vide, V. Mitrana and J.M. Sempere, Networks of evolutionary processors. Acta Inf.39 (2003) 517–529. Zbl1060.68046MR1993630
  5. [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. Zbl1211.68199
  6. [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. Zbl1054.68084MR1605238
  7. [7] E. Csuhaj-Varjú and S. Verlan, On length-separating test tube systems. Natural Comput.7 (2008) 167–181. Zbl1146.68372MR2403209
  8. [8] E. Csuhaj-Varjú, L. Kari and G. Paun, Test tube distributed systems based on splicing. Comput. Artif. Intelligence15 (1996) 211–232. Zbl0852.68051MR1405413
  9. [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. Zbl1230.68125
  10. [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. Zbl1175.68161MR2454740
  11. [11] C. Drăgoi, F. Manea and V. Mitrana, Accepting networks of evolutionary processors with filtered connections. J. UCS13 (2007) 1598–1614. Zbl1175.68160MR2390239
  12. [12] R. Loos, On accepting networks of splicing processors of size 3, in Proc. CiE. Lect. Notes Comput. Sci.4497 (2007) 497–506. Zbl1151.68418MR2646261
  13. [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. Zbl1160.68014MR2493988
  14. [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. Zbl1113.68401
  15. [15] F. Manea, C. Martín-Vide and V. Mitrana, Accepting networks of splicing processors : complexity results. Theor. Comput. Sci.371 (2007) 72–82. Zbl1108.68052MR2298667
  16. [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. Zbl1230.68072
  17. [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. Zbl1116.68463
  18. [18] C. Martín-Vide and V. Mitrana, Networks of evolutionary processors : Results and perspectives, in Molecular Computational Models : Unconventional Approaches (2005) 78–114. Zbl1060.68046
  19. [19] G. Paun, G. Rozenberg and A. Salomaa, DNA computing – new computing paradigms. Texts in Theor. Comput. Sci. Springer (1998). Zbl1069.68559MR1724525
  20. [20] G. Rozenberg and A. Salomaa, Handbook of Formal Languages. Springer-Verlag, New York, Inc., Secaucus, NJ, USA (1997). Zbl0866.68057

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.