Nondeterministic seedless oritatami systems and hardness of testing their equivalence

DOI10.1007/S11047-017-9661-YzbMATH Open1528.68119OpenAlexW2772803310MaRDI QIDQ6061982FDOQ6061982

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

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

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)

Cites Work

• On Relating Time and Space to Size and Depth
• Complexity classes in models of cellular computing with membranes
• 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)