Skip to main content
Erschienen in: Natural Computing 2/2008

01.06.2008

On length-separating test tube systems

verfasst von: Erzsébet Csuhaj-Varjú, Sergey Verlan

Erschienen in: Natural Computing | Ausgabe 2/2008

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this article we introduce a new variant of test tube systems based on splicing where the communication of the words among the test tubes is based on filtering by their lengths. The model, called length-separating test tube systems, is motivated by the gel electrophoresis laboratory technique. We prove that these constructs, even with restricted size parameters, simulate the Turing machines. We also discuss some natural restrictions and generalizations of the model, which may be used to find efficient ways to realize DNA transformations in the laboratory.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Adleman LM (1994) Molecular computation of solutions to combinatorial problems. Science 226:1021–1024CrossRef Adleman LM (1994) Molecular computation of solutions to combinatorial problems. Science 226:1021–1024CrossRef
Zurück zum Zitat Csuhaj-Varjú E, Kari L, Păun G (1996) Test tube distributed systems based on splicing. Comput Artif Intell 15(2–3):211–232MATH Csuhaj-Varjú E, Kari L, Păun G (1996) Test tube distributed systems based on splicing. Comput Artif Intell 15(2–3):211–232MATH
Zurück zum Zitat Guarnieri F, Fliss M, Bacroft C (1996) Making DNA add. Science 273(12):220–223CrossRef Guarnieri F, Fliss M, Bacroft C (1996) Making DNA add. Science 273(12):220–223CrossRef
Zurück zum Zitat Head T (1987) Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors. Bull Math Biol 49(6):737–759MathSciNetMATH Head T (1987) Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors. Bull Math Biol 49(6):737–759MathSciNetMATH
Zurück zum Zitat Hopcroft J, Motwani R, Ullman J (2001) Introduction to automata theory, languages, and computation, 2nd edn. Addison-Wesley, Reading, Mass Hopcroft J, Motwani R, Ullman J (2001) Introduction to automata theory, languages, and computation, 2nd edn. Addison-Wesley, Reading, Mass
Zurück zum Zitat Khodor Y, Khodor J, Knight TF Jr (2002) Experimental confirmation of the basic principles of length-only discrimination. In: Jonoska N, Seeman NC (eds) DNA7. Lecture notes in computer science, vol 2340. Springer-Verlag, Berlin, pp 223–230 Khodor Y, Khodor J, Knight TF Jr (2002) Experimental confirmation of the basic principles of length-only discrimination. In: Jonoska N, Seeman NC (eds) DNA7. Lecture notes in computer science, vol 2340. Springer-Verlag, Berlin, pp 223–230
Zurück zum Zitat Margenstern M, Rogozhin Y (1999) A universal time-varying distributed H System of degree 2. Biosystems 52:73–80CrossRef Margenstern M, Rogozhin Y (1999) A universal time-varying distributed H System of degree 2. Biosystems 52:73–80CrossRef
Zurück zum Zitat Păun G, Rozenberg G, Salomaa A (1998) DNA computing: new computing paradigms. Springer Verlag, BerlinMATH Păun G, Rozenberg G, Salomaa A (1998) DNA computing: new computing paradigms. Springer Verlag, BerlinMATH
Zurück zum Zitat Rozenberg G, Salomaa A (1997) Handbook of formal languages, vols I–III. Springer Verlag, BerlinMATH Rozenberg G, Salomaa A (1997) Handbook of formal languages, vols I–III. Springer Verlag, BerlinMATH
Zurück zum Zitat Verlan S (2004a) Communicating distributed H systems with alternating filters. In: Jonoska N, Paun G, Rozenberg G (eds) Aspects of molecular computing. Essays Dedicated to Tom Head on the occasion of his 70th birthday. Lecture notes in computer science, vol 2950, pp 367–384. Springer Verlag, Berlin Verlan S (2004a) Communicating distributed H systems with alternating filters. In: Jonoska N, Paun G, Rozenberg G (eds) Aspects of molecular computing. Essays Dedicated to Tom Head on the occasion of his 70th birthday. Lecture notes in computer science, vol 2950, pp 367–384. Springer Verlag, Berlin
Zurück zum Zitat Verlan S (2004b) Head systems and applications to bio-informatics. PhD thesis, University of Metz, France Verlan S (2004b) Head systems and applications to bio-informatics. PhD thesis, University of Metz, France
Zurück zum Zitat Verlan S (2005) A boundary result on enhanced time-varying distributed H systems with parallel computations. Theor Comput Sci 344(2–3):226–242CrossRefMathSciNetMATH Verlan S (2005) A boundary result on enhanced time-varying distributed H systems with parallel computations. Theor Comput Sci 344(2–3):226–242CrossRefMathSciNetMATH
Metadaten
Titel
On length-separating test tube systems
verfasst von
Erzsébet Csuhaj-Varjú
Sergey Verlan
Publikationsdatum
01.06.2008
Verlag
Springer Netherlands
Erschienen in
Natural Computing / Ausgabe 2/2008
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-007-9034-z

Weitere Artikel der Ausgabe 2/2008

Natural Computing 2/2008 Zur Ausgabe