Advertisement
Published in:
2014 | OriginalPaper | Chapter
On Decidability and Closure Properties of Language Classes with Respect to Bio-operations
Author : Oscar H. Ibarra
Published in: DNA Computing and Molecular Programming
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present general results that are useful in showing closure and decidable properties of large classes of languages with respect to biologically-inspired operations. We use these results to prove new decidability results and closure properties of some classes of languages under hairpin-inversion, pseudo-inversion, and other bio-operations. We also provide a new approach for proving the undecidability of problems involving bio-operations for which the usual method of reduction to the undecidability of the Post Correspondence Problem (PCP) may not be easy to apply. Our closure and decidability results strengthen or generalize previous results.