Name
Abstract | ||
|---|---|---|
Multi-valued Model Checking is an extension of classical, two-valued model checking with multi-valued logic. Multi-valuedness has been proved useful in expressing additional information such as incompleteness, uncertainty, and many others, but with the cost of time and space complexity. This paper addresses this problem, and proposes a new algorithm for Multi-valued Model Checking. While Chechik et al. have extended BDD-based Symbolic Model Checking algorithm to the multi-valued case, our algorithm extends Bounded Model Checking (BMC), which can generate a counterexample of minimum length efficiently (if any). A notable feature of our algorithm is that it directly generates conjunctive normal forms, and never reduces multi-valued formulas into many slices of two-valued formulas. To achieve this feature, we extend the BMC algorithm to the multi-valued case and also devise a new translation of multi-valued propositional formulas. Finally, we show experimental results and compare the performance of our algorithm with that of a reduction-based algorithm. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-88387-6_8 | ATVA |
Keywords | Field | DocType |
bmc algorithm,multi-valued model checking,multi-valued formula,multi-valued case,multi-valued bounded model checking,model checking,bdd-based symbolic model checking,multi-valued propositional formula,new algorithm,direct algorithm,multi-valued logic,reduction-based algorithm,conjunctive normal form,space complexity | Abstraction model checking,Discrete mathematics,Model checking,Computer science,Algorithm,Theoretical computer science,Conjunctive normal form,Partial order reduction,Propositional formula,Propositional variable,Symbolic trajectory evaluation,Bounded function | Conference |
Volume | ISSN | Citations |
5311 | 0302-9743 | 1 |
PageRank | References | Authors |
0.37 | 11 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jefferson O. Andrade | 1 | 2 | 0.72 |
| Yukiyoshi Kameyama | 2 | 171 | 17.29 |