Conference paper

BOUAJJANI Ahmed, HABERMEHL Peter, HOLÍK Lukáš, TOUILI Tayssir and VOJNAR Tomáš. Antichain-based Universality and Inclusion Testing over Nondeterministic Finite Tree Automata. In: Implementation and Application of Automata. Berlin: Springer Verlag, 2008, pp. 57-67. ISBN 978-3-540-70843-8.
Publication language:english
Original title:Antichain-based Universality and Inclusion Testing over Nondeterministic Finite Tree Automata
Title (cs):Testování univerzality stromových automatů založené na protiřetězcích
Pages:57-67
Proceedings:Implementation and Application of Automata
Conference:13th International Conference on Implementation and Application of Automata -- CIAA'08
Series:LNCS 5148
Place:Berlin, DE
Year:2008
ISBN:978-3-540-70843-8
Publisher:Springer Verlag
Keywords
unversality, tree automata, antichain, abstract regular tree model checking
Annotation
We propose new antichain-based algorithms for
checking universality and inclusion of nondeterministic tree automata (NTA).
We have
implemented these algorithms in a prototype tool and our experiments
show that they provide a significant improvement over the traditional
determinisation-based approaches. We use our
antichain-based inclusion checking algorithm to build an abstract regular tree
model checking framework based entirely on NTA. We
show the significantly improved efficiency of this  framework through a series of experiments with verifying various programs over dynamic linked tree-shaped data structures.
BibTeX:
@INPROCEEDINGS{
   author = {Ahmed Bouajjani and Peter Habermehl and Luk{\'{a}}{\v{s}}
	Hol{\'{i}}k and Tayssir Touili and Tom{\'{a}}{\v{s}} Vojnar},
   title = {Antichain-based Universality and Inclusion Testing over
	Nondeterministic Finite Tree Automata},
   pages = {57--67},
   booktitle = {Implementation and Application of Automata},
   series = {LNCS 5148},
   year = {2008},
   location = {Berlin, DE},
   publisher = {Springer Verlag},
   ISBN = {978-3-540-70843-8},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=8672}
}

Your IPv4 address: 54.224.21.195
Switch to IPv6 connection

DNSSEC [dnssec]