When Simulation Meets Antichains

Parosh Aziz Abdulla 1 Yu-Fang Chen 1 Lukáš Holík 2 Richard Mayr 3 Tomáš Vojnar 2
1 Uppsala University
2 Brno University of Technology
3 School of Engineering - University of Edinburgh
Abstract : We describe a new and more efficient algorithm for checking universality and language inclusion on nondeterministic finite word automata (NFA) and tree automata (TA). To the best of our knowledge, the antichain-based approach proposed by De Wulf et al. was the most efficient one so far. Our idea is to exploit a simulation relation on the states of finite automata to accelerate the antichain-based algorithms. Normally, a simulation relation can be obtained fairly efficiently, and it can help the antichain-based approach to prune out a large portion of unnecessary search paths.We evaluate the performance of our new method on NFA/TA obtained from random regular expressions and from the intermediate steps of regular model checking. The results show that our approach significantly outperforms the previous antichain-based approach in most of the experiments
Type de document :
Communication dans un congrès
TACAS'10, the 16th International Conference on Tools And Algorithms for the Construction and Analysis of Systems, Mar 2010, Paphos, Cyprus. 2010
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00460294
Contributeur : Emmanuelle Grousset <>
Soumis le : vendredi 26 février 2010 - 16:30:43
Dernière modification le : jeudi 26 octobre 2017 - 16:34:02
Document(s) archivé(s) le : vendredi 18 juin 2010 - 20:27:56

Fichier

yu-fang-tacas10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00460294, version 1

Collections

CONNECT

Citation

Parosh Aziz Abdulla, Yu-Fang Chen, Lukáš Holík, Richard Mayr, Tomáš Vojnar. When Simulation Meets Antichains. TACAS'10, the 16th International Conference on Tools And Algorithms for the Construction and Analysis of Systems, Mar 2010, Paphos, Cyprus. 2010. 〈inria-00460294〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

157

Téléchargements de fichiers

179

Contact


archive-ouverte@inria.fr