Technická zpráva

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.
Jazyk publikace:angličtina
Název publikace:Efficient Inclusion Checking on Explicit and Semi-Symbolic Tree Automata
Název (cs):Efektivní testování inkluze explicitních a polo-symbolických stromových automatů
Strany:22
Místo vydání:FIT-TR-2011-04, Brno, CZ
Rok:2011
Vydavatel:Fakulta informačních technologií VUT v Brně
URL:http://www.fit.vutbr.cz/~ilengal/pub/FIT-TR-2011-04.pdf [HTML]
Klíčová slova
tree automata, binary decision diagrams, language inclusion, downward inclusion checking, symbolic encoding
Anotace
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.
BibTeX:
@TECHREPORT{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=9708}
}

Vaše IPv4 adresa: 34.236.190.216
Přepnout na https