Detail publikace

An Efficient Finite Tree Automata Library: The Design of BDD-based Semi-symbolic Algorithms for Nondeterministic Finite Tree Automata

LENGÁL Ondřej. An Efficient Finite Tree Automata Library: The Design of BDD-based Semi-symbolic Algorithms for Nondeterministic Finite Tree Automata. Saarbrücken: Lambert Academic Publishing, 2012. ISBN 978-3-659-27069-7.
Název česky
Efektivní knihovna pro práci s konečnými stromovými automaty: návrh semi-symbolických algoritmů pro práci s nedeterministickými konečnými stromovými automaty, jež jsou založeny na BDD
Typ
odborná monografie
Jazyk
angličtina
Autoři
Abstrakt

Mnoho současných počítačových systémů používá dynamické datové či řídicí struktury předem neomezené velikosti. Tyto datové struktury mají často charakter stromů nebo se dají zakódovat jako stromy s některými dodatečnými ukazateli nad stromovou kostrou. Této skutečnosti využívají některé v současné době intenzivně studované techniky formální verifikace, které reprezentují nekonečně mnoho stavů konečným stromovým automatem. Nicméně v současnosti neexistuje efektivní a flexibilní implementace knihovny pro stromové automaty, která by byla pro tyto techniky vhodná. Cílem této diplomové práce je takovouto knihovnu poskytnout. Předložený text nejdříve popisuje základy teorie konečných stromových automatů a regulárních stromových jazyků. Dále jsou prozkoumány existující implementace knihoven pro stromové automaty a různé verifikační techniky pro systémy se stromovou strukturou. Poté se text zaobírá návrhem reprezentace stromového automatu a algoritmů provádějících standardní jazykové operace nad touto reprezentací, načež následuje popis implementace knihovny. Prostřednictvím provedených experimentů ukazujeme, že knihovna může konkurovat ostatním dostupným knihovnám pro práci se stromovými automaty, přičemž její výkon v určitých oblastech je řádově vyšší.

Rok
2012
Strany
64
ISBN
978-3-659-27069-7
Vydavatel
Lambert Academic Publishing
Místo
Saarbrücken, DE
BibTeX
@BOOK{FITPUB10206,
   author = "Ond\v{r}ej Leng\'{a}l",
   title = "An Efficient Finite Tree Automata Library: The Design of BDD-based Semi-symbolic Algorithms for Nondeterministic Finite Tree Automata",
   pages = 64,
   year = 2012,
   location = "Saarbr{\"{u}}cken, DE",
   publisher = "Lambert Academic Publishing",
   ISBN = "978-3-659-27069-7",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/10206"
}
Nahoru