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. Lecture Notes in Computer Science, 2011, vol. 2011, no. 6996, p. 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
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)
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
243–258
Časopis
Lecture Notes in Computer Science, roč. 2011, č. 6996, ISSN 0302-9743
BibTeX 
@article{BUT76407,
  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",
  journal="Lecture Notes in Computer Science",
  year="2011",
  volume="2011",
  number="6996",
  pages="243--258",
  issn="0302-9743"
}
Nahoru