Language Containment Checking with Nondeterministic BDDs
Bernd Finkbeiner6 
| (6) |
Computer Science Department, Stanford University, Stanford, CA, 94305-9045 |
Abstract
Checking for language containment between nondeterministic ω-automata is a central task in automata-based hierarchical verification.
We present a symbolic procedure for language containment checking between two Büuchi automata. Our algorithm avoids determinization
by intersecting the implementation automaton with the complement of the specification automaton as an alternating automaton.
We present a fix-point algorithm for the emptiness check of alternating automata. The main data structure is a nondeterministic
extension of binary decision diagrams that canonically represents sets of Boolean functions.
This research was supported in part by the National Science Foundation grant CCR-99-00984-001, by ARO grant DAAG55-98-1-0471,
by ARO/MURI grant DAAH04-96-1-0341, by ARPA/Army contract DABT63-96-C-0096, and by ARPA/AirForce contracts F33615-00-C-1693
and F33615-99-C-3014.
References secured to subscribers.