Emptiness Check of Powerset Buchi Automata using Inclusion Tests

Bratislava, Slovak Republic July 10-July 13

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/ACSD.2007.49

Seventh International Conference on A ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Souheib Baarir Articles by Alexandre Duret-Lutz

	ASCII Text	x
	Souheib Baarir, Alexandre Duret-Lutz, "Emptiness Check of Powerset Buchi Automata using Inclusion Tests," Application of Concurrency to System Design, International Conference on, pp. 41-50, Seventh International Conference on Application of Concurrency to System Design (ACSD 2007), 2007.

	BibTex	x
	@article{ 10.1109/ACSD.2007.49, author = {Souheib Baarir and Alexandre Duret-Lutz}, title = {Emptiness Check of Powerset Buchi Automata using Inclusion Tests}, journal ={Application of Concurrency to System Design, International Conference on}, volume = {0}, year = {2007}, issn = {1550-4808}, pages = {41-50}, doi = {http://doi.ieeecomputersociety.org/10.1109/ACSD.2007.49}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Application of Concurrency to System Design, International Conference on TI - Emptiness Check of Powerset Buchi Automata using Inclusion Tests SN - 1550-4808 SP41 EP50 A1 - Souheib Baarir, A1 - Alexandre Duret-Lutz, PY - 2007 KW - null VL - 0 JA - Application of Concurrency to System Design, International Conference on ER -

Souheib Baarir, Universite Pierre et Marie Curie, France

Alexandre Duret-Lutz, Universite Pierre et Marie Curie, France

We introduce two emptiness checks for Buchi automata whose states represent sets that may include each other. The first is equivalent to a traditional emptiness check but uses inclusion tests to direct the on-the-fly construction of the automaton. The second is impressively faster but may return false negatives. We illustrate and benchmark the improvement on a symmetry-based reduction.

Citation:

Souheib Baarir, Alexandre Duret-Lutz, "Emptiness Check of Powerset Buchi Automata using Inclusion Tests," acsd, pp.41-50, Seventh International Conference on Application of Concurrency to System Design (ACSD 2007), 2007

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.