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
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