Detail publikace

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

HAMMER, J.; KŘIVKA, Z. Practical Aspects of Membership Problem of Watson-Crick Context-free Grammars. In Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications. Electronic Proceedings in Theoretical Computer Science, EPTCS. Debrecen: School of Computer Science and Engineering, University of New South Wales, 2022. p. 88-111. ISSN: 2075-2180.
Název česky
Praktické aspekty problému členství Watson-Crick bezkontextových gramatik
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Hammer Jan, Ing.
Křivka Zbyněk, Ing., Ph.D. (UIFS)
URL
Klíčová slova

Watson-Crick languages, DNA computing, formal grammars, membership problem, state space search

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, EPTCS, č. 367, ISSN 2075-2180
Sborník
Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications
Vydavatel
School of Computer Science and Engineering, University of New South Wales
Místo
Debrecen
DOI
10.4204/EPTCS.367.7
UT WoS
001047943700008
EID Scopus
2-s2.0-85137611300
BibTeX 
@inproceedings{BUT178926,
  author="Jan {Hammer} and Zbyněk {Křivka}",
  title="Practical Aspects of Membership Problem of Watson-Crick Context-free Grammars",
  booktitle="Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications",
  year="2022",
  journal="Electronic Proceedings in Theoretical Computer Science, EPTCS",
  number="367",
  pages="88--111",
  publisher="School of Computer Science and Engineering, University of New South Wales",
  address="Debrecen",
  doi="10.4204/EPTCS.367.7",
  issn="2075-2180",
  url="http://eptcs.web.cse.unsw.edu.au/paper.cgi?NCMA2022.7"
}
Nahoru