Detail publikace

Efficient Inclusion Checking on Explicit and Semi-Symbolic Tree Automata

HOLÍK, L.; LENGÁL, O.; ŠIMÁČEK, J.; VOJNAR, T. Efficient Inclusion Checking on Explicit and Semi-Symbolic Tree Automata. FIT-TR-2011-04, Brno: Faculty of Information Technology BUT, 2011. p. 0-0.
Název česky
Efektivní testování inkluze explicitních a polo-symbolických stromových automatů
Typ
zpráva odborná
Jazyk
anglicky
Autoři
Holík Lukáš, doc. Mgr., Ph.D. (UITS)
Lengál Ondřej, Ing., Ph.D. (UITS)
Šimáček Jiří, Ing., Ph.D.
Vojnar Tomáš, prof. Ing., Ph.D. (UITS)
URL
Klíčová slova

tree automata, binary decision diagrams, language inclusion, downward inclusion checking, symbolic encoding

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
Faculty of Information Technology BUT
Místo
FIT-TR-2011-04, Brno
BibTeX 
@techreport{BUT192739,
  author="Lukáš {Holík} and Ondřej {Lengál} and Jiří {Šimáček} and Tomáš {Vojnar}",
  title="Efficient Inclusion Checking on Explicit and Semi-Symbolic Tree Automata",
  year="2011",
  publisher="Faculty of Information Technology BUT",
  address="FIT-TR-2011-04, Brno",
  pages="22",
  url="http://www.fit.vutbr.cz/~ilengal/pub/FIT-TR-2011-04.pdf"
}
Nahoru