Linear encodings of bounded LTL model checking
We consider the problem of bounded model checking (BMC) for linear temporal logic (LTL).
We present several efficient encodings that have size linear in the bound. Furthermore, we …
We present several efficient encodings that have size linear in the bound. Furthermore, we …
Incremental and complete bounded model checking for full PLTL
K Heljanko, T Junttila, T Latvala - … CAV 2005, Edinburgh, Scotland, UK, July …, 2005 - Springer
Bounded model checking is an efficient method for finding bugs in system designs. The
major drawback of the basic method is that it cannot prove properties, only disprove them …
major drawback of the basic method is that it cannot prove properties, only disprove them …
An incremental algorithm to check satisfiability for bounded model checking
HS Jin, F Somenzi - Electronic Notes in Theoretical Computer Science, 2005 - Elsevier
In Bounded Model Checking (BMC), the search for counterexamples of increasing lengths is
translated into a sequence of satisfiability (SAT) checks. It is natural to try to exploit the …
translated into a sequence of satisfiability (SAT) checks. It is natural to try to exploit the …
[图书][B] Parameterized Complexity in the Polynomial Hierarchy
R de Haan - 2019 - Springer
Parameterized Complexity in the Polynomial Hierarchy Page 1 Ronald de Haan LNCS
11880 Extending Parameterized Complexity Theory to Higher Levels of the Hierarchy …
11880 Extending Parameterized Complexity Theory to Higher Levels of the Hierarchy …
Fixed-parameter tractable reductions to SAT
Today's SAT solvers have an enormous importance and impact in many practical settings.
They are used as efficient back-end to solve many NP-complete problems. However, many …
They are used as efficient back-end to solve many NP-complete problems. However, many …
Traveling tournament scheduling: A systematic evaluation of simulated annealling
P Van Hentenryck, Y Vergados - … on Integration of Artificial Intelligence (AI) …, 2006 - Springer
This paper considers all the variants of the traveling tournament problem (TTP) proposed in
[17, 7] to abstract the salient features of major league baseball (MLB) in the United States …
[17, 7] to abstract the salient features of major league baseball (MLB) in the United States …
Efficient techniques for directed test generation using incremental satisfiability
Functional validation is a major bottleneck in the current SOC design methodology. While
specification-based validation techniques have proposed several promising ideas, the time …
specification-based validation techniques have proposed several promising ideas, the time …
Learning interpretable heuristics for WalkSAT
Y Interian, S Bernardini - arXiv preprint arXiv:2307.04608, 2023 - arxiv.org
Local search algorithms are well-known methods for solving large, hard instances of the
satisfiability problem (SAT). The performance of these algorithms crucially depends on …
satisfiability problem (SAT). The performance of these algorithms crucially depends on …
Conditional lexicographic orders in constraint satisfaction problems
RJ Wallace, N Wilson - International Conference on Integration of Artificial …, 2006 - Springer
The lexicographically-ordered CSP (“lexicographic CSP” for short) combines a simple
representation of preferences with the feasibility constraints of ordinary CSPs. Preferences …
representation of preferences with the feasibility constraints of ordinary CSPs. Preferences …
An algebraic approach to the complexity of generalized conjunctive queries
M Bauland, P Chapdelaine, N Creignou… - … Conference on Theory …, 2004 - Springer
Conjunctive-query containment is considered as a fundamental problem in database query
evaluation and optimization. Kolaitis and Vardi pointed out that constraint satisfaction and …
evaluation and optimization. Kolaitis and Vardi pointed out that constraint satisfaction and …