Bounded Model Checking for Weak Alternating Buchi Automata (2006)
AUTHORS:
Heljanko Keijo
,
Junttila Tommi
,
Keinänen Misa
,
\ Martin Lange,
Latvala Timo
BOOKTITLE:
Proceedings of the 18th International Conference on Computer Aided\ Verification (CAV'2006)
SERIES:
Lecture Notes in Computer Science
VOLUME:
4144
PAGES:
95--108
URL:
http://www.tcs.hut.fi/~timo/publications/
@inproceedings{ HelJunKeiLanLat:CAV06, editor = "Ball, Thomas and Jones, Robert B.", author = "Heljanko, Keijo and Junttila, Tommi and Keinänen, Misa and \, Martin Lange and Latvala, Timo", ignoreurl = "http://dx.doi.org/10.1007/11817963_12", publisher = "Springer-Verlag", title = {Bounded Model Checking for Weak Alternating {B{\"u}chi} Automata}, url = "http://www.tcs.hut.fi/~timo/publications/", series = "Lecture Notes in Computer Science", booktitle = "Proceedings of the 18th International Conference on Computer Aided\ Verification (CAV'2006)", address = "Seattle, WA, USA", abstract = {We present an incremental bounded model checking encoding into propositional satisfiability where the property specification is expressed as a weak alternating B{\"u}chi automaton (WABA)\ . The encoding is linear in the specification, or, more exactly ${\mathcal O}(\arrowvert I \arrowvert + k \cdot \arrowvert T \arrowvert + k \cdot \arrowvert \delta \arrowvert)$, where $\arrowvert I \arrowvert$ is the size of the initial state predicate, $k$ is the bound, $\arrowvert T \arrowvert$ is the size of the transition relation, and $\arrowvert \delta \arrowvert$ is the size of the WABA transition relation. Minimal length counterexamples can also be found by increasing the encoding size to be quadratic in the number of states in the largest component of the WABA. The proposed encoding can be used to implement more efficient bounded model checking algorithms for $\omega$-regular industrial specification languages such as Accellera's Property Specification Language (PSL). Encouraging experimental results on a prototype implementation are reported\ .}, month = "August", volume = "4144", flags = "copy,ACPT", year = "2006", keywords = {Weak Alternating B{\"u}chi Automata, Bounded Model Checking, NuSMV,\ PSL}, pages = "95--108" }