Jazyky bez vazeb: formalizace, maximalita a metody konstrukce

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F47813059%3A19240%2F04%3A00012610" target="_blank" >RIV/47813059:19240/04:00012610 - 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.

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GP201%2F02%2FP079" target="_blank" >GP201/02/P079: Distribuované modely kognitivních výpočtů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2004

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 statě ve sborníku

DNA 10, Tenth International Meeting on DNA Computing

ISBN

—

ISSN

—

e-ISSN

—

Počet stran výsledku

10

Strana od-do

16-25

Název nakladatele

University of Milano--Bicocca

Místo vydání

Miláno

Místo konání akce

Milano

Datum konání akce

1. 1. 2004

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—