Publication Details

Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing

ABDULLA Parosh A., CLEMENTE Lorenzo, HOLÍK Lukáš, HONG Chih-Duo, CHEN Yu-Fang, MAYR Richard and VOJNAR Tomáš. Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing. In: Computer Aided Verification. Lecture Notes in Computer Science, vol. 6174. Berlín: Springer Verlag, 2010, pp. 132-147. ISBN 978-3-642-14294-9.
Czech title
Simulační pokrytí v Ramseyho testu univerzality a Inkluze Büchiho automatů
Type
conference paper
Language
english
Authors
Abdulla Parosh A. (Uppsala)
Clemente Lorenzo (UEDIN)
Holík Lukáš, doc. Mgr., Ph.D. (DITS FIT BUT)
Hong Chih-Duo (ASIN)
Chen Yu-Fang (ASIN)
Mayr Richard (UEDIN)
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT)
URL
Keywords

Büchi automata, universality, language inclusion, Ramsey-based methods, simulation subsumption

Abstract

There are two main classes of methods for checking universality
and language inclusion of Büchi-automata: Rank-based methods
and Ramsey-based methods. While rank-based methods have a better
worst-case complexity, Ramsey-based methods have been shown to be
quite competitive in practice. Previously, it was also shown (for universality checking) that a simple subsumption technique, which avoids exploration of certain cases, greatly improves the performance of the Ramsey-based method. Here, we present a much more general subsumption technique for the Ramsey-based method, which is based on using simulation preorder on the states of the Büchi-automata. This technique applies to both universality and inclusion checking, yielding a substantial performance gain over the previously known simple subsumption approach.

Published
2010
Pages
132-147
Proceedings
Computer Aided Verification
Series
Lecture Notes in Computer Science
Volume
6174
Conference
22nd International Conference on Computer-Aided Verification, Edinburgh, GB
ISBN
978-3-642-14294-9
Publisher
Springer Verlag
Place
Berlín, DE
BibTeX 
@INPROCEEDINGS{FITPUB9270,
   author = "A. Parosh Abdulla and Lorenzo Clemente and Luk\'{a}\v{s} Hol\'{i}k and Chih-Duo Hong and Yu-Fang Chen and Richard Mayr and Tom\'{a}\v{s} Vojnar",
   title = "Simulation Subsumption in Ramsey-Based B{\"{u}}chi Automata Universality and Inclusion Testing",
   pages = "132--147",
   booktitle = "Computer Aided Verification",
   series = "Lecture Notes in Computer Science",
   volume = 6174,
   year = 2010,
   location = "Berl\'{i}n, DE",
   publisher = "Springer Verlag",
   ISBN = "978-3-642-14294-9",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9270"
}
Back to top