Anzeige
Erschienen in:
01.06.2016
On decidability and closure properties of language classes with respect to bio-operations
Erschienen in: Natural Computing | Ausgabe 2/2016
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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 bio-operations such hairpin-inversion, the recently studied operation of pseudo-inversion, and other bio-operations. We also provide techniques for proving undecidability results. In particular, we give a new approach for proving the undecidability of problems for which the usual method of reduction to the undecidability of the Post Correspondence Problem seems hard to apply. Our closure and decidability results strengthen or generalize previous results.