Conference paper

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. Berlín: Springer Verlag, 2010, pp. 132-147. ISBN 978-3-642-14294-9.
Publication language:english
Original title:Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing
Title (cs):Simulační pokrytí v Ramseyho testu univerzality a Inkluze Büchiho automatů
Proceedings:Computer Aided Verification
Conference:22nd International Conference on Computer-Aided Verification
Series:LNCS 6174
Place:Berlín, DE
Publisher:Springer Verlag
Büchi automata, universality, language inclusion, Ramsey-based methods, simulation subsumption
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.
   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 = {LNCS 6174},
   year = {2010},
   location = {Berl{\'{i}}n, DE},
   publisher = {Springer Verlag},
   ISBN = {978-3-642-14294-9},
   language = {english},
   url = {}

Your IPv4 address:
Switch to https