O formálních jazycích a slovech bez vlásenek

Kód výsledku v IS VaVaI

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

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

On hairpin-free words and languages

Popis výsledku v původním jazyce

The paper examines the concept of hairpin-free words motivated from the biocomputing and bioinformatics fields. Hairpin (-free) DNA structures have numerous applications to DNA computing and molecular genetics in general. A word is called hairpin-free ifit cannot be written in the form xvy theta(v)z, with certain additional conditions, for an involution theta (a function theta with the property that theta(2) equals the identity function). We consider three involutions relevant to DNA computing: a) themirror image function, b) the DNA complementarity function over the DNA alphabet {A, C, G, T} which associates A with T and C with G, and c) the Watson-Crick involution which is the composition of the previous two. We study elementary properties and finiteness of hairpin (-free) languages w.r.t. the involutions a) and c). Maximal length of hairpin-free words is also examined. Finally, descriptional complexity of maximal hairpin-free languages is determined.

Název v anglickém jazyce

On hairpin-free words and languages

Popis výsledku anglicky

The paper examines the concept of hairpin-free words motivated from the biocomputing and bioinformatics fields. Hairpin (-free) DNA structures have numerous applications to DNA computing and molecular genetics in general. A word is called hairpin-free ifit cannot be written in the form xvy theta(v)z, with certain additional conditions, for an involution theta (a function theta with the property that theta(2) equals the identity function). We consider three involutions relevant to DNA computing: a) themirror image function, b) the DNA complementarity function over the DNA alphabet {A, C, G, T} which associates A with T and C with G, and c) the Watson-Crick involution which is the composition of the previous two. We study elementary properties and finiteness of hairpin (-free) languages w.r.t. the involutions a) and c). Maximal length of hairpin-free words is also examined. Finally, descriptional complexity of maximal hairpin-free languages is determined.

Druh

D - Stať ve sborníku

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

DEVELOPMENTS IN LANGUAGE THEORY

ISBN

3-540-26546-5

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

—

Název nakladatele

—

Místo vydání

Berlin

Místo konání akce

Palermo

Datum konání akce

1. 1. 2005

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

WRD - Celosvětová akce

Kód UT WoS článku

—