Nondeterministic seedless oritatami systems and hardness of testing their equivalence

DOI10.1007/S11047-017-9661-YMaRDI QIDQ6061982zbMATH OpenOpenAlexFDO

Authors Yo-Sub Han, Hwee Kim, Makoto Ota, Shinnosuke Seki

Publication date 30 November 2023

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11047-017-9661-y

zbMATH Keywords

nondeterminismself-assemblyoritatami systemRNA cotranscriptional folding

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Recommendations

• Nondeterministic seedless oritatami systems and hardness of testing their equivalence
• scientific article; zbMATH DE number 2019634
• On randomized semi-algebraic test complexity
• scientific article; zbMATH DE number 2080931
• Deterministic semi-Thue systems and variants of Post correspondence problem
• Nondeterministic functions and the existence of optimal proof systems
• scientific article; zbMATH DE number 4172379
• scientific article; zbMATH DE number 1500525
• Hardness of equivalence checking for composed finite-state systems

Cites work

• Complexity classes in models of cellular computing with membranes
• On Relating Time and Space to Size and Depth
• Programming biomolecules that fold greedily during transcription

Cited in

(3)

• On the complexity of monitoring Orchids signatures, and recurrence equations
• Impossibility of strict assembly of infinite fractals by oritatami
• Transcript design problem of oritatami systems

This page was built for publication: Nondeterministic seedless oritatami systems and hardness of testing their equivalence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6061982)