Time and space complexity for splicing systems

DOI10.1007/s00224-008-9161-7zbMath1206.68117OpenAlexW2039382155MaRDI QIDQ1959375

Remco Loos, Ogihara, Mitsunori

Publication date: 6 October 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-008-9161-7

zbMATH Keywords

computational complexityDNA computingsplicing systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors
• Splicing semigroups of dominoes and DNA
• Computing by splicing
• Regularity of splicing languages
• Complexity theory for splicing systems
• An alternative definition of splicing
• Relationships between nondeterministic and deterministic tape complexities
• Time-bounded grammars and their languages
• Non-preserving splicing with delay