Detail publikace

Practical Aspects of Membership Problem of Watson-Crick Context-free Grammars

HAMMER Jan a KŘIVKA Zbyněk. Practical Aspects of Membership Problem of Watson-Crick Context-free Grammars. In: Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications . Debrecen: School of Computer Science and Engineering, University of New South Wales, 2022, s. 88-111. ISSN 2075-2180. Dostupné z: http://eptcs.web.cse.unsw.edu.au/paper.cgi?NCMA2022.7
Název česky
Praktické aspekty problému členství Watson-Crick bezkontextových gramatik
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Hammer Jan, Ing. (FIT VUT)
Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT)
URL
Abstrakt

Příspěvek je zaměřen na Watson-Crick jazyky inspirované DNA výpočty, jejich modely a algoritmy pro rozhodnutí problému členství. Analyzuje nedávno představený algoritmus nazvaný WK-CYK a představuje algoritmus prohledávání stavového prostoru, který je založen na prohledávání do šířky, ale pro efektivnost a praktičnost využívá řadu optimalizací a heuristik. Klíčové jsou heuristiky pro ořezávání stavového prostoru (odstranění mrtvých větví) a heuristiky vybírající nejslibnější větev pro následující prohledávání.

Oba algoritmy jsou testovány na 20 různých Watson-Crick gramatikách (40 včetně jejich varianty v Chomského normální formě). Ačkoli WK-CYK je schopen v rozumném čase rozhodovat členství vstupních řetězců pouze délky mezi 30-50 symboly, tak je jeho výkon velmi konzistentní nezávisle na složitosti gramatiky nebo vstupní věty. Prohledávání stavového prostoru je většinou (89-98 % případů) efektivnější a schopné  zpracovat vstupy délky stovek až tisíců symbolů. Algoritmus prohledávání stavového prostoru je dobrým nástrojem pro praktické testování problém členství pro Watson-Crick bezkontextové gramatiky a dobrým základem pro další vylepšení.

Rok
2022
Strany
88-111
Časopis
Electronic Proceedings in Theoretical Computer Science, č. 367, ISSN 2075-2180
Sborník
Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications
Konference
12th International Workshop on Non-Classical Models of Automata and Applications, Debrecen, HU
Vydavatel
School of Computer Science and Engineering, University of New South Wales
Místo
Debrecen, HU
DOI
10.4204/EPTCS.367.7
EID Scopus
2-s2.0-85137611300
BibTeX 
@INPROCEEDINGS{FITPUB12770,
   author = "Jan Hammer and Zbyn\v{e}k K\v{r}ivka",
   title = "Practical Aspects of Membership Problem of Watson-Crick Context-free Grammars",
   pages = "88--111",
   booktitle = "Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications ",
   journal = "Electronic Proceedings in Theoretical Computer Science",
   number = 367,
   year = 2022,
   location = "Debrecen, HU",
   publisher = "School of Computer Science and Engineering, University of New South Wales",
   ISSN = "2075-2180",
   doi = "10.4204/EPTCS.367.7",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12770"
}
Nahoru