Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-14T18:00:02.447Z Has data issue: false hasContentIssue false
  • English
  • Français

Generating Networks of Splicing Processors

Published online by Cambridge University Press:  30 July 2012

Jürgen Dassow,
Florin Manea and
Bianca Truthe
Jürgen Dassow
Affiliation:
Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, PSF 4120, 39016 Magdeburg, Germany. dassow@iws.cs.uni-magdeburg.de, truthe@iws.cs.uni-magdeburg.de
Florin Manea
Affiliation:
Christian-Albrechts-Universität zu Kiel, Institut für Informatik, Christian-Albrechts-Platz 4, 24098 Kiel, Germany; flm@informatik.uni-kiel.deFaculty of Mathematics and Computer Science, University of Bucharest, Academiei 14, 010014 Bucharest, Romania
Bianca Truthe
Affiliation:
Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, PSF 4120, 39016 Magdeburg, Germany. dassow@iws.cs.uni-magdeburg.de, truthe@iws.cs.uni-magdeburg.de

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 toaccepting networks of splicing processors. We show that all recursively enumerablelanguages can be generated by GNSPs with only nine processors. We also show, by directsimulation, that two other variants of this computing model, where the communicationbetween processors is conducted in different ways, have the same computational power.

Keywords

Splicingnetworks of splicing processorsnetworks of splicing processors with filtered connectionscomputational completeness

References

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. CrossRef
Alhazov, A., Csuhaj-Varjú, E., Martín-Vide, C. and Rogozhin, Y., On the size of computationally complete hybrid networks of evolutionary processors. Theor. Comput. Sci. 410 (2009) 3188–3197. Google Scholar
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. CrossRef
Castellanos, J., Martín-Vide, C., Mitrana, V. and Sempere, J.M., Networks of evolutionary processors. Acta Inf. 39 (2003) 517–529. Google Scholar
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. CrossRef
Csuhaj-Varjú, E. and Salomaa, A., Networks of Parallel Language Processors, in New Trends in Formal Languages – Control, Cooperation and Combinatorics. Lect. Notes Comput. Sci. 1218 (1997) 299–318. Google Scholar
Csuhaj-Varjú, E. and Verlan, S., On length-separating test tube systems. Natural Comput. 7 (2008) 167–181. Google Scholar
Csuhaj-Varjú, E., Kari, L. and Paun, G., Test tube distributed systems based on splicing. Comput. Artif. Intelligence 15 (1996) 211–232. Google Scholar
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. CrossRef
Drăgoi, C. and Manea, F., On the descriptional complexity of accepting networks of evolutionary processors with filtered connections. Int. J. Found. Comput. Sci. 19 (2008) 1113–1132. Google Scholar
Drăgoi, C., Manea, F. and Mitrana, V., Accepting networks of evolutionary processors with filtered connections. J. UCS 13 (2007) 1598–1614. Google Scholar
R. Loos, On accepting networks of splicing processors of size 3, in Proc. CiE. Lect. Notes Comput. Sci. 4497 (2007) 497–506. CrossRef
Loos, R., Manea, F. and Mitrana, V., On small, reduced, and fast universal accepting networks of splicing processors. Theor. Comput. Sci. 410 (2009) 406–416. Google Scholar
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. CrossRef
Manea, F., Martín-Vide, C. and Mitrana, V., Accepting networks of splicing processors : complexity results. Theor. Comput. Sci. 371 (2007) 72–82. Google Scholar
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.
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. CrossRef
C. Martín-Vide and V. Mitrana, Networks of evolutionary processors : Results and perspectives, in Molecular Computational Models : Unconventional Approaches (2005) 78–114. CrossRef
G. Paun, G. Rozenberg and A. Salomaa, DNA computing – new computing paradigms. Texts in Theor. Comput. Sci. Springer (1998).
G. Rozenberg and A. Salomaa, Handbook of Formal Languages. Springer-Verlag, New York, Inc., Secaucus, NJ, USA (1997).