Két hasonló, egyszerű természet-motivált számítási modell, a Watson-Crick automata és a sztring építő rendszer kapcsolatának vizsgálata

Dátum
Folyóirat címe
Folyóirat ISSN
Kötet címe (évfolyam száma)
Kiadó
Absztrakt

A dolgozatban a Watson-Crick automaták (WK automaták) és a sztring építő rendszerek (String Assembling Sytems - SAS rendszerek) kapcsolatát vizsgáljuk. Mindkét számítási modell bevezetését az élő sejtekben található DNS molekulák szerkezete inspirálta, mindketten a DNS molekulák kettős spirálját imitáló "kétszálú" sztringekkel dolgoznak. A kétszálú sztringek egy "felső" és egy "alsó" betűsorozatból állnak, melyekben az egyes pozíciókon (alul és felül) lévő betűk között az összekapcsolódó DNS bázispárok közötti Watson-Crick komplementaritáshoz hasonló komplementaritási reláció áll fenn. A WK automaták a két sztring szál olvasására külön olvasófejekkel ellátott véges automaták, az SAS rendszerek pedig kétszálú sztringekkel reprezentált "építőkövekből" a természetben is gyakran megfigyelt önszerveződő (self assembly) módon kétszálú sztringeket generáló rendszerek. A modellek számítási erejét a két fejjel végigolvasva elfogadható, illetve az építőelemekből generálható kétszálú sztring halmazok (nyelvek) jellemzik. A dolgozatban a két modell feltűnő hasonlóságai mellett a különbségeiket is részletesebben megvizsgáljuk, az egyes változataik által elfogadott illetve generált nyelvek összehasonlításán keresztül új eredményeket mutatunk be számítási erejük egymáshoz való viszonyáról, melyeket röviden az alábbiak szerint foglalhatunk össze. Általános esetben a WK automaták számítási ereje nagyobb mint az SAS rendszereké (1. tétel), ezért a pontosabb összehasonlítás kedvéért korlátozott állapotszámú WK automatákat vizsgálunk. Tudjuk, hogy az állapotmentes (azaz egyállapotú) WK automaták által elfogadott nyelvek egy bevezető jelet a szavak elé illesztve SAS rendszerekkel is generálhatók (2. tétel), továbbá van olyan nyelv, ami SAS rendszerrel generálható, de állapotmentes WK automatával nem fogadható el (3., 4. és 5. tétel). A kérdéses nyelvosztályok viszonyát azonban nem sikerült teljesen tisztáznunk: nem világos, hogy az állapotmentes WK automatákkal elfogadható nyelvek bevezető jel nélkül is generálhatóak-e SAS rendszerrel. Ha sikerülne ezt bizonyítani, akkor az SAS rendszerekkel generálható nyelvek osztálya tartalmazná az állapotmentes WK automaták nyelveit, ha sikerülne cáfolni, akkor bebizonyosodna a nyelvosztályok összemérhetetlensége.

Leírás
Kulcsszavak
számítástudomány, formális nyelvek, automaták, Watson-Crick automata, string assembling system
Forrás