2006 | OriginalPaper | Buchkapitel
Bounded Model Checking for Weak Alternating Büchi Automata
verfasst von : Keijo Heljanko, Tommi Junttila, Misa Keinänen, Martin Lange, Timo Latvala
Erschienen in: Computer Aided Verification
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present an incremental bounded model checking encoding into propositional satisfiability where the property specification is expressed as a weak alternating Bü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
ω
-regular industrial specification languages such as Accellera’s Property Specification Language (PSL). Encouraging experimental results on a prototype implementation are reported.