Detail publikace

Efficient Inclusion Checking on Explicit and Semi-Symbolic Tree Automata

HOLÍK Lukáš, LENGÁL Ondřej, ŠIMÁČEK Jiří a VOJNAR Tomáš. Efficient Inclusion Checking on Explicit and Semi-Symbolic Tree Automata. FIT-TR-2011-04, Brno: Fakulta informačních technologií VUT v Brně, 2011.
Název česky
Efektivní testování inkluze explicitních a polo-symbolických stromových automatů
Typ
technická zpráva
Jazyk
angličtina
Autoři
URL
Abstrakt

Tento článek pojednává o několika problémech jež se vážou k efektivnímu použití stromových automatů ve formální verifikaci. Nejdříve je popsán nový efektivní algoritmus pro testování inkluze nedeterministických stromových automatů. Algoritmus prochází automatem směrem shora dolů, využívajíc protiřetězce a simulace ke svému urychlení. Výsledky sady experimentů ukazují, že tento přístup často výrazně převyšuje dosud nejčastěji používané testování inkluze zdola nahoru. Dále je navžena nová polo-symbolická reprezentace nedeterministických stromových automatů, jež je vhodná pro automaty s velkými abecedami, spolu s algoritmy pro testování inkluze shora dolů i zdola nahoru využívajících této reprezentace. Výsledky experimentů porovnávající tyto algoritmy znovu ukazují, ze testování inkluze shora dolů je velmi často lepší než testování inkluze zdola nahoru.

Rok
2011
Strany
22
Vydavatel
Fakulta informačních technologií VUT v Brně
Místo
FIT-TR-2011-04, Brno, CZ
BibTeX
@TECHREPORT{FITPUB9708,
   author = "Luk\'{a}\v{s} Hol\'{i}k and Ond\v{r}ej Leng\'{a}l and Ji\v{r}\'{i} \v{S}im\'{a}\v{c}ek and Tom\'{a}\v{s} Vojnar",
   title = "Efficient Inclusion Checking on Explicit and Semi-Symbolic Tree Automata",
   pages = 22,
   year = 2011,
   location = "FIT-TR-2011-04, Brno, CZ",
   publisher = "Faculty of Information Technology BUT",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9708"
}
Nahoru