DNA jazyky bez vazeb: formalizace, maximalita a konstrukční metody

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F47813059%3A19240%2F05%3A%230001877" target="_blank" >RIV/47813059:19240/05:#0001877 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Bond-free languages: Formalizations, maximality and construction methods

Popis výsledku v původním jazyce

The problem of negative design of DNA languages is addressed, that is, properties and construction methods of large sets of words that prevent undesired bonds when used in DNA computations. We recall a few existing formalizations of the problem and thendefine the property of sim-bond-freedom, where sim is a similarity relation between words. We show that this property is decidable for context-free languages and polynomial-time decidable for regular languages. The maximality of this property also turnsout to be decidable for regular languages and polynomial-time decidable for an important case of the Hamming similarity. Then we consider various construction methods for Hamming bond-free languages, including the recently introduced method of templates,and obtain a complete structural characterization of all maximal Hamming bond-free languages. This result is applicable to the theta-k-code property introduced by Jonoska and Mahalingam.

Název v anglickém jazyce

Bond-free languages: Formalizations, maximality and construction methods

Popis výsledku anglicky

The problem of negative design of DNA languages is addressed, that is, properties and construction methods of large sets of words that prevent undesired bonds when used in DNA computations. We recall a few existing formalizations of the problem and thendefine the property of sim-bond-freedom, where sim is a similarity relation between words. We show that this property is decidable for context-free languages and polynomial-time decidable for regular languages. The maximality of this property also turnsout to be decidable for regular languages and polynomial-time decidable for an important case of the Hamming similarity. Then we consider various construction methods for Hamming bond-free languages, including the recently introduced method of templates,and obtain a complete structural characterization of all maximal Hamming bond-free languages. This result is applicable to the theta-k-code property introduced by Jonoska and Mahalingam.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2005

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

ISSN

0129-0541

e-ISSN

—

Svazek periodika

5

Číslo periodika v rámci svazku

16

Stát vydavatele periodika

SG - Singapurská republika

Počet stran výsledku

32

Strana od-do

—

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—