The Experts below are selected from a list of 9189 Experts worldwide ranked by ideXlab platform
Sharad Malik - One of the best experts on this subject based on the ideXlab platform.
-
validating the result of a quantified Boolean Formula qbf solver theory and practice
Asia and South Pacific Design Automation Conference, 2005Co-Authors: Sharad MalikAbstract:Despite the increasing use of QBF solvers, current QBF solvers do not provide for any mechanism to verify their results. This paper demonstrates a methodology for independently validating the results of a DLL based QBF solver using the traces generated during the solving process. It also presents a mechanism to extract small unsatisfiable subFormulas, called cores, from unsatisfiable QBF instances.
-
analysis of search based algorithms for satisfiability of propositional and quantified Boolean Formulas arising from circuit state space diameter problems
Theory and Applications of Satisfiability Testing, 2004Co-Authors: Daijue Tang, Darsh Ranjan, Sharad MalikAbstract:The sequential circuit state space diameter problem is an important problem in sequential verification. Bounded model checking is complete if the state space diameter of the system is known. By unrolling the transition relation, the sequential circuit state space diameter problem can be Formulated as either a series of Boolean satisfiability (SAT) problems or an evaluation for satisfiability of a Quantified Boolean Formula (QBF). Thus far neither the SAT based technique that uses sophisticated SAT solvers, nor QBF evaluations for the various QBF Formulations for this have fared well in practice. The poor performance of the QBF evaluations is blamed on the relative immaturity of QBF solvers, with hope that ongoing research in QBF solvers could lead to practical success here. Most existing QBF algorithms, such as those based on the DPLL SAT algorithm, are search based. We show that using search based QBF algorithms to calculate the state space diameter of sequential circuits with existing problem Formulations is no better than using SAT to solve this problem. This result holds independent of the representation of the QBF Formula. This result is important as it highlights the need to explore non-search based or hybrid of search and non-search based QBF algorithms for the sequential circuit state space diameter problem.
-
analysis of search based algorithms for satisfiability of quantified Boolean Formulas arising from circuit state space diameter problems
Theory and Applications of Satisfiability Testing, 2004Co-Authors: Daijue Tang, Darsh Ranjan, Sharad MalikAbstract:The sequential circuit state space diameter problem is an important problem in sequential verification. Bounded model checking is complete if the state space diameter of the system is known. By unrolling the transition relation, the sequential circuit state space diameter problem can be Formulated as an evaluation for satisfiability of a Quantified Boolean Formula (QBF). This has prompted research in QBFs in the verification community. Most of existing QBF algorithms, such as those based on the DPLL SAT algorithm, are search based. We show that using search based QBF algorithms to calculate the state space diameter of sequential circuits with existing problem Formulations is no better than an explicit state space enumeration method. This result holds independent of the representation of the QBF Formula. This result is important as it highlights the need to explore non-search based or hybrid of search and non-search based QBF algorithms for the sequential circuit state space diameter problem.
-
towards a symmetric treatment of satisfaction and conflicts in quantified Boolean Formula evaluation
Lecture Notes in Computer Science, 2002Co-Authors: Lintao Zhang, Sharad MalikAbstract:In this paper, we describe a new framework for evaluating Quantified Boolean Formulas (QBF). The new framework is based on the Davis-Putnam (DPLL) search algorithm. In existing DPLL based QBF algorithms, the problem database is represented in Conjunctive Normal Form (CNF) as a set of clauses, implications are generated from these clauses, and backtracking in the search tree is chronological. In this work, we augment the basic DPLL algorithm with conflict driven learning as well as satisfiability directed implication and learning. In addition to the traditional clause database, we add a cube database to the data structure. We show that cubes can be used to generate satisfiability directed implications similar to conflict directed implications generated by the clauses. We show that in a QBF setting, conflicting leaves and satisfying leaves of the search tree both provide valuable information to the solver in a symmetric way. We have implemented our algorithm in the new QBF solver Quaffle. Experimental results show that for some test cases, satisfiability directed implication and learning significantly prunes the search.
Rafael Penaloza - One of the best experts on this subject based on the ideXlab platform.
-
automata based axiom pinpointing
Journal of Automated Reasoning, 2010Co-Authors: Franz Baader, Rafael PenalozaAbstract:Axiom pinpointing has been introduced in description logics (DL) to help the user understand the reasons why consequences hold by computing minimal subsets of the knowledge base that have the consequence in question (MinA). Most of the pinpointing algorithms described in the DL literature are obtained as extensions of tableau-based reasoning algorithms for computing consequences from DL knowledge bases. In this paper, we show that automata-based algorithms for reasoning in DLs and other logics can also be extended to pinpointing algorithms. The idea is that the tree automaton constructed by the automata-based approach can be transformed into a weighted tree automaton whose so-called behaviour yields a pinpointing Formula, i.e., a monotone Boolean Formula whose minimal valuations correspond to the MinAs. We also develop an approach for computing the behaviour of a given weighted tree automaton. We use the DL $\mathcal{SI}$ as well as Linear Temporal Logic (LTL) to illustrate our new pinpointing approach.
-
automata based axiom pinpointing
International Joint Conference on Automated Reasoning, 2008Co-Authors: Franz Baader, Rafael PenalozaAbstract:Axiom pinpointing has been introduced in description logics (DL) to help the user understand the reasons why consequences hold by computing minimal subsets of the knowledge base that have the consequence in question (MinA). Most of the pinpointing algorithms described in the DL literature are obtained as extensions of tableau-based reasoning algorithms for computing consequences from DL knowledge bases. In this paper, we show that automata-based algorithms for reasoning in DLs can also be extended to pinpointing algorithms. The idea is that the tree automaton constructed by the automata-based approach can be transformed into a weighted tree automaton whose so-called behaviour yields a pinpointing Formula, i.e., a monotone Boolean Formula whose minimal valuations correspond to the MinAs. We also develop an approach for computing the behaviour of a given weighted tree automaton.
Tomoyuki Yamakami - One of the best experts on this subject based on the ideXlab platform.
-
the 2cnf Boolean Formula satisfiability problem and the linear space hypothesis
arXiv: Computational Complexity, 2017Co-Authors: Tomoyuki YamakamiAbstract:We aim at investigating the solvability/insolvability of nondeterministic logarithmic-space (NL) decision, search, and optimization problems parameterized by size parameters using simultaneously polynomial time and sub-linear space on multi-tape deterministic Turing machines. We are particularly focused on a special NL-complete problem, 2SAT---the 2CNF Boolean Formula satisfiability problem---parameterized by the number of Boolean variables. It is shown that 2SAT with $n$ variables and $m$ clauses can be solved simultaneously polynomial time and $(n/2^{c\sqrt{\log{n}}})\, polylog(m+n)$ space for an absolute constant $c>0$. This fact inspires us to propose a new, practical working hypothesis, called the linear space hypothesis (LSH), which states that 2SAT$_3$---a restricted variant of 2SAT in which each variable of a given 2CNF Formula appears at most 3 times in the form of literals---cannot be solved simultaneously in polynomial time using strictly "sub-linear" (i.e., $m(x)^{\varepsilon}\, polylog(|x|)$ for a certain constant $\varepsilon\in(0,1)$) space on all instances $x$. An immediate consequence of this working hypothesis is $\mathrm{L}\neq\mathrm{NL}$. Moreover, we use our hypothesis as a plausible basis to lead to the insolvability of various NL search problems as well as the nonapproximability of NL optimization problems. For our investigation, since standard logarithmic-space reductions may no longer preserve polynomial-time sub-linear-space complexity, we need to introduce a new, practical notion of "short reduction." It turns out that, parameterized with the number of variables, $\overline{\mathrm{2SAT}_3}$ is complete for a syntactically restricted version of NL, called Syntactic NL$_{\omega}$, under such short reductions. This fact supports the legitimacy of our working hypothesis.
-
the 2cnf Boolean Formula satisfiability problem and the linear space hypothesis
Mathematical Foundations of Computer Science, 2017Co-Authors: Tomoyuki YamakamiAbstract:We aim at investigating the solvability/insolvability of nondeterministic logarithmic-space (NL) decision, search, and optimization problems parameterized by size parameters using simultaneously polynomial time and sub-linear space on multi-tape deterministic Turing machines. We are particularly focused on a special NL-complete problem, 2SAT - the 2CNF Boolean Formula satisfiability problem-parameterized by the number of Boolean variables. It is shown that 2SAT with n variables and m clauses can be solved simultaneously polynomial time and (n/2^{c sqrt{log(n)}}) polylog(m+n) space for an absolute constant c>0. This fact inspires us to propose a new, practical working hypothesis, called the linear space hypothesis (LSH), which states that 2SAT_3-a restricted variant of 2SAT in which each variable of a given 2CNF Formula appears as literals in at most 3 clauses-cannot be solved simultaneously in polynomial time using strictly "sub-linear" (i.e., n^{epsilon} polylog(n) for a certain constant epsilon in (0,1)) space. An immediate consequence of this working hypothesis is L neq NL. Moreover, we use our hypothesis as a plausible basis to lead to the insolvability of various NL search problems as well as the nonapproximability of NL optimization problems. For our investigation, since standard logarithmic-space reductions may no longer preserve polynomial-time sub-linear-space complexity, we need to introduce a new, practical notion of "short reduction." It turns out that overline{2SAT}_3 is complete for a restricted version of NL, called Syntactic NL or simply SNL, under such short reductions. This fact supports the legitimacy of our working hypothesis.
Franz Baader - One of the best experts on this subject based on the ideXlab platform.
-
automata based axiom pinpointing
Journal of Automated Reasoning, 2010Co-Authors: Franz Baader, Rafael PenalozaAbstract:Axiom pinpointing has been introduced in description logics (DL) to help the user understand the reasons why consequences hold by computing minimal subsets of the knowledge base that have the consequence in question (MinA). Most of the pinpointing algorithms described in the DL literature are obtained as extensions of tableau-based reasoning algorithms for computing consequences from DL knowledge bases. In this paper, we show that automata-based algorithms for reasoning in DLs and other logics can also be extended to pinpointing algorithms. The idea is that the tree automaton constructed by the automata-based approach can be transformed into a weighted tree automaton whose so-called behaviour yields a pinpointing Formula, i.e., a monotone Boolean Formula whose minimal valuations correspond to the MinAs. We also develop an approach for computing the behaviour of a given weighted tree automaton. We use the DL $\mathcal{SI}$ as well as Linear Temporal Logic (LTL) to illustrate our new pinpointing approach.
-
automata based axiom pinpointing
International Joint Conference on Automated Reasoning, 2008Co-Authors: Franz Baader, Rafael PenalozaAbstract:Axiom pinpointing has been introduced in description logics (DL) to help the user understand the reasons why consequences hold by computing minimal subsets of the knowledge base that have the consequence in question (MinA). Most of the pinpointing algorithms described in the DL literature are obtained as extensions of tableau-based reasoning algorithms for computing consequences from DL knowledge bases. In this paper, we show that automata-based algorithms for reasoning in DLs can also be extended to pinpointing algorithms. The idea is that the tree automaton constructed by the automata-based approach can be transformed into a weighted tree automaton whose so-called behaviour yields a pinpointing Formula, i.e., a monotone Boolean Formula whose minimal valuations correspond to the MinAs. We also develop an approach for computing the behaviour of a given weighted tree automaton.
Luc De Raedt - One of the best experts on this subject based on the ideXlab platform.
-
inference and learning in probabilistic logic programs using weighted Boolean Formulas
arXiv: Artificial Intelligence, 2013Co-Authors: Daan Fierens, Guy Van Den Broeck, Ingo Thon, Bernd Gutmann, Joris Renkens, Dimitar Shterionov, Gerda Janssens, Luc De RaedtAbstract:Probabilistic logic programs are logic programs in which some of the facts are annotated with probabilities. This paper investigates how classical inference and learning tasks known from the graphical model community can be tackled for probabilistic logic programs. Several such tasks such as computing the marginals given evidence and learning from (partial) interpretations have not really been addressed for probabilistic logic programs before. The first contribution of this paper is a suite of efficient algorithms for various inference tasks. It is based on a conversion of the program and the queries and evidence to a weighted Boolean Formula. This allows us to reduce the inference tasks to well-studied tasks such as weighted model counting, which can be solved using state-of-the-art methods known from the graphical model and knowledge compilation literature. The second contribution is an algorithm for parameter estimation in the learning from interpretations setting. The algorithm employs Expectation Maximization, and is built on top of the developed inference algorithms. The proposed approach is experimentally evaluated. The results show that the inference algorithms improve upon the state-of-the-art in probabilistic logic programming and that it is indeed possible to learn the parameters of a probabilistic logic program from interpretations.