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. Lecture Notes in Computer Science, roč. 2011, č. 6996, s. 243-258. ISSN 0302-9743.
Název česky
Efektivní testování inkluze explicitních a polo-symbolických stromových automatů
Typ
článek v časopise
Jazyk
angličtina
Autoři
Holík Lukáš, doc. Mgr., Ph.D. (UITS FIT VUT)
Lengál Ondřej, Ing., Ph.D. (UITS FIT VUT)
Šimáček Jiří, Ing., Ph.D. (UITS FIT VUT)
Vojnar Tomáš, prof. Ing., Ph.D. (UITS FIT VUT)
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
243-258
Časopis
Lecture Notes in Computer Science, roč. 2011, č. 6996, ISSN 0302-9743
Vydavatel
Springer Verlag
BibTeX 
@ARTICLE{FITPUB9703,
   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 = "243--258",
   journal = "Lecture Notes in Computer Science",
   volume = 2011,
   number = 6996,
   year = 2011,
   ISSN = "0302-9743",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9703"
}
Nahoru