The Experts below are selected from a list of 876 Experts worldwide ranked by ideXlab platform
Erik Rosenthal - One of the best experts on this subject based on the ideXlab platform.
-
Knowledge Compilation: Decomposable Negation Normal Form versus Linkless Formulas?
2015Co-Authors: Neil V. Murray, Erik RosenthalAbstract:Abstract. Decomposable Negation Normal Form (DNNF) was developed primar-ily for knowledge compilation. Formulas in DNNF are linkless, in Negation nor-mal Form (NNF), and have the property that atoms are not shared across conjunc-tions. Full dissolvents are linkless NNF Formulas that do not in general have the latter property. However, many of the applications of DNNF can be obtained with full dissolvents. Two additional methods — regular tableaux and semantic factor-ing — are shown to produce equivalent DNNF. A class of Formulae is presented on which earlier DNNF conversion techniques are necessarily exponential; path dissolution and semantic factoring handle these Formulae in linear time.
-
ISMIS - Normal Forms for knowledge compilation
Lecture Notes in Computer Science, 2005Co-Authors: Reiner Hähnle, Neil V. Murray, Erik RosenthalAbstract:A class of Formulas called factored Negation Normal Form is introduced. They are closely related to BDDs, but there is a DPLL-like tableau procedure for computing them that operates in PSPACE.Ordered factored Negation Normal Form provides a canonical representation for any boolean function. Reduction strategies are developed that provide a unique reduced factored Negation Normal Form. These compilation techniques work well with negated Form as input, and it is shown that any logical Formula can be translated into negated Form in linear time.
-
Linearity and regularity with Negation Normal Form
Theoretical Computer Science, 2004Co-Authors: Reiner Hähnle, Neil V. Murray, Erik RosenthalAbstract:Proving completeness of NC-resolution under a linear restriction has been elusive; it is proved here for Formulas in Negation Normal Form. The proof uses a generalization of the AndersonBledsoe excess literal argument, which was developed for resolution. That result is extended to NC-resolution with partial replacement. A simple proof of the completeness of regular, connected tableaux for Formulas in conjunctive Normal Form is also presented. These techniques are then used to establish the completeness of regular, connected tableaux for Formulas in Negation Normal Form.
-
tableaux path dissolution and decomposable Negation Normal Form for knowledge compilation
Theorem Proving with Analytic Tableaux and Related Methods, 2003Co-Authors: Neil V. Murray, Erik RosenthalAbstract:Decomposable Negation Normal Form (DNNF) was developed primarily for knowledge compilation. Formulas in DNNF are linkless, in Negation Normal Form (NNF), and have the property that atoms are not shared across conjunctions. Full dissolvents are linkless NNF Formulas that do not in general have the latter property. However, many of the applications of DNNF can be obtained with full dissolvents. Two additional methods — regular tableaux and semantic factoring — are shown to produce equivalent DNNF. A class of Formulae is presented on which earlier DNNF conversion techniques are necessarily exponential; path dissolution and semantic factoring handle these Formulae in linear time.
-
TABLEAUX - Tableaux, Path Dissolution, and Decomposable Negation Normal Form for Knowledge Compilation
Lecture Notes in Computer Science, 2003Co-Authors: Neil V. Murray, Erik RosenthalAbstract:Decomposable Negation Normal Form (DNNF) was developed primarily for knowledge compilation. Formulas in DNNF are linkless, in Negation Normal Form (NNF), and have the property that atoms are not shared across conjunctions. Full dissolvents are linkless NNF Formulas that do not in general have the latter property. However, many of the applications of DNNF can be obtained with full dissolvents. Two additional methods — regular tableaux and semantic factoring — are shown to produce equivalent DNNF. A class of Formulae is presented on which earlier DNNF conversion techniques are necessarily exponential; path dissolution and semantic factoring handle these Formulae in linear time.
Neil V. Murray - One of the best experts on this subject based on the ideXlab platform.
-
Knowledge Compilation: Decomposable Negation Normal Form versus Linkless Formulas?
2015Co-Authors: Neil V. Murray, Erik RosenthalAbstract:Abstract. Decomposable Negation Normal Form (DNNF) was developed primar-ily for knowledge compilation. Formulas in DNNF are linkless, in Negation nor-mal Form (NNF), and have the property that atoms are not shared across conjunc-tions. Full dissolvents are linkless NNF Formulas that do not in general have the latter property. However, many of the applications of DNNF can be obtained with full dissolvents. Two additional methods — regular tableaux and semantic factor-ing — are shown to produce equivalent DNNF. A class of Formulae is presented on which earlier DNNF conversion techniques are necessarily exponential; path dissolution and semantic factoring handle these Formulae in linear time.
-
ISMIS - Normal Forms for knowledge compilation
Lecture Notes in Computer Science, 2005Co-Authors: Reiner Hähnle, Neil V. Murray, Erik RosenthalAbstract:A class of Formulas called factored Negation Normal Form is introduced. They are closely related to BDDs, but there is a DPLL-like tableau procedure for computing them that operates in PSPACE.Ordered factored Negation Normal Form provides a canonical representation for any boolean function. Reduction strategies are developed that provide a unique reduced factored Negation Normal Form. These compilation techniques work well with negated Form as input, and it is shown that any logical Formula can be translated into negated Form in linear time.
-
Linearity and regularity with Negation Normal Form
Theoretical Computer Science, 2004Co-Authors: Reiner Hähnle, Neil V. Murray, Erik RosenthalAbstract:Proving completeness of NC-resolution under a linear restriction has been elusive; it is proved here for Formulas in Negation Normal Form. The proof uses a generalization of the AndersonBledsoe excess literal argument, which was developed for resolution. That result is extended to NC-resolution with partial replacement. A simple proof of the completeness of regular, connected tableaux for Formulas in conjunctive Normal Form is also presented. These techniques are then used to establish the completeness of regular, connected tableaux for Formulas in Negation Normal Form.
-
tableaux path dissolution and decomposable Negation Normal Form for knowledge compilation
Theorem Proving with Analytic Tableaux and Related Methods, 2003Co-Authors: Neil V. Murray, Erik RosenthalAbstract:Decomposable Negation Normal Form (DNNF) was developed primarily for knowledge compilation. Formulas in DNNF are linkless, in Negation Normal Form (NNF), and have the property that atoms are not shared across conjunctions. Full dissolvents are linkless NNF Formulas that do not in general have the latter property. However, many of the applications of DNNF can be obtained with full dissolvents. Two additional methods — regular tableaux and semantic factoring — are shown to produce equivalent DNNF. A class of Formulae is presented on which earlier DNNF conversion techniques are necessarily exponential; path dissolution and semantic factoring handle these Formulae in linear time.
-
TABLEAUX - Tableaux, Path Dissolution, and Decomposable Negation Normal Form for Knowledge Compilation
Lecture Notes in Computer Science, 2003Co-Authors: Neil V. Murray, Erik RosenthalAbstract:Decomposable Negation Normal Form (DNNF) was developed primarily for knowledge compilation. Formulas in DNNF are linkless, in Negation Normal Form (NNF), and have the property that atoms are not shared across conjunctions. Full dissolvents are linkless NNF Formulas that do not in general have the latter property. However, many of the applications of DNNF can be obtained with full dissolvents. Two additional methods — regular tableaux and semantic factoring — are shown to produce equivalent DNNF. A class of Formulae is presented on which earlier DNNF conversion techniques are necessarily exponential; path dissolution and semantic factoring handle these Formulae in linear time.
Adnan Darwiche - One of the best experts on this subject based on the ideXlab platform.
-
CP - On Compiling CNF into Decision-DNNF
Lecture Notes in Computer Science, 2014Co-Authors: Umut Oztok, Adnan DarwicheAbstract:Decision-DNNF is a strict subset of decomposable Negation Normal Form (DNNF) that plays a key role in analyzing the complexity of model counters (the searches perFormed by these counters have their traces in Decision-DNNF). This paper presents a number of results on Decision-DNNF. First, we introduce a new notion of CNF width and provide an algorithm that compiles CNFs into Decision-DNNFs in time and space that are exponential only in this width. The new width strictly dominates the treewidth of the CNF primal graph: it is no greater and can be bounded when the treewidth of the primal graph is unbounded. This new result leads to a tighter bound on the complexity of model counting. Second, we show that the output of the algorithm can be converted in linear time to a sentential decision diagram (SDD), which leads to a tighter bound on the complexity of compiling CNFs into SDDs.
-
On Decomposability and Interaction Functions
2013Co-Authors: Knot Pipatsrisawat, Adnan DarwicheAbstract:Abstract. A Formal notion of a Boolean-function decomposition was introduced recently and used to provide lower bounds on various representations of Boolean functions, which are subsets of decomposable Negation Normal Form (DNNF). This notion has introduced a fundamental optimization problem for DNNF representations, which calls for computing decompositions of minimal size for a given partition of the function variables. We consider the problem of computing optimal decompositions in this paper for general Boolean functions and those represented using CNFs. We introduce the notion of an interaction function, which characterizes the relationship between two sets of variables and can Form the basis of obtaining such decompositions. We contrast the use of these functions to the current practice of computing decompositions, which is based on heuristic methods that can be viewed as using approximations of interaction functions. We show that current methods can lead to decompositions that are exponentially larger than optimal decompositions, pinpoint the specific reasons for this lack of optimality, and finally present empirical results that illustrate some characteristics of interaction functions in contrast to their approximations.
-
ECAI - On Decomposability and Interaction Functions
2010Co-Authors: Knot Pipatsrisawat, Adnan DarwicheAbstract:A Formal notion of a Boolean-function decomposition was introduced recently and used to provide lower bounds on various representations of Boolean functions, which are subsets of decomposable Negation Normal Form (DNNF). This notion has introduced a fundamental optimization problem for DNNF representations, which calls for computing decompositions of minimal size for a given partition of the function variables. We consider the problem of computing optimal decompositions in this paper for general Boolean functions and those represented using CNFs. We introduce the notion of an interaction function, which characterizes the relationship between two sets of variables and can Form the basis of obtaining such decompositions. We contrast the use of these functions to the current practice of computing decompositions, which is based on heuristic methods that can be viewed as using approximations of interaction functions. We show that current methods can lead to decompositions that are exponentially larger than optimal decompositions, pinpoint the specific reasons for this lack of optimality, and finally present empirical results that illustrate some characteristics of interaction functions in contrast to their approximations.
-
AAAI - A lower bound on the size of decomposable Negation Normal Form
2010Co-Authors: Knot Pipatsrisawat, Adnan DarwicheAbstract:We consider in this paper the size of a Decomposable Negation Normal Form (DNNF) that respects a given vtree (known as structured DNNF). This representation of propositional knowledge bases was introduced recently and shown to include OBDD as a special case (an OBDD variable ordering is a special type of vtree). We provide a lower bound on the size of any structured DNNF and discuss three particular instances of this bound, which correspond to three distinct subsets of structured DNNF (including OBDD). We show that our lower bound subsumes the influential Sieling and Wegener's lower bound for OBDDs, which is typically used for identifying variable orderings that will cause a blowup in the OBDD size. We show that our lower bound allows for similar usage but with respect to vtrees, which provide structure for DNNFs in the same way that variable orderings provide structure for OBDDs. We finally discuss some of the theoretical and practical implications of our lower bound.
-
a lower bound on the size of decomposable Negation Normal Form
National Conference on Artificial Intelligence, 2010Co-Authors: Knot Pipatsrisawat, Adnan DarwicheAbstract:We consider in this paper the size of a Decomposable Negation Normal Form (DNNF) that respects a given vtree (known as structured DNNF). This representation of propositional knowledge bases was introduced recently and shown to include OBDD as a special case (an OBDD variable ordering is a special type of vtree). We provide a lower bound on the size of any structured DNNF and discuss three particular instances of this bound, which correspond to three distinct subsets of structured DNNF (including OBDD). We show that our lower bound subsumes the influential Sieling and Wegener's lower bound for OBDDs, which is typically used for identifying variable orderings that will cause a blowup in the OBDD size. We show that our lower bound allows for similar usage but with respect to vtrees, which provide structure for DNNFs in the same way that variable orderings provide structure for OBDDs. We finally discuss some of the theoretical and practical implications of our lower bound.
Reiner Hähnle - One of the best experts on this subject based on the ideXlab platform.
-
ISMIS - Normal Forms for knowledge compilation
Lecture Notes in Computer Science, 2005Co-Authors: Reiner Hähnle, Neil V. Murray, Erik RosenthalAbstract:A class of Formulas called factored Negation Normal Form is introduced. They are closely related to BDDs, but there is a DPLL-like tableau procedure for computing them that operates in PSPACE.Ordered factored Negation Normal Form provides a canonical representation for any boolean function. Reduction strategies are developed that provide a unique reduced factored Negation Normal Form. These compilation techniques work well with negated Form as input, and it is shown that any logical Formula can be translated into negated Form in linear time.
-
Linearity and regularity with Negation Normal Form
Theoretical Computer Science, 2004Co-Authors: Reiner Hähnle, Neil V. Murray, Erik RosenthalAbstract:Proving completeness of NC-resolution under a linear restriction has been elusive; it is proved here for Formulas in Negation Normal Form. The proof uses a generalization of the AndersonBledsoe excess literal argument, which was developed for resolution. That result is extended to NC-resolution with partial replacement. A simple proof of the completeness of regular, connected tableaux for Formulas in conjunctive Normal Form is also presented. These techniques are then used to establish the completeness of regular, connected tableaux for Formulas in Negation Normal Form.
-
TABLEAUX - Some Remarks on Completeness, Connection Graph Resolution and Link Deletion
Lecture Notes in Computer Science, 1998Co-Authors: Reiner Hähnle, Neil V. Murray, Erik RosenthalAbstract:A new completeness proof that generalizes the Anderson-Bledsoe excess literal argument is developed for connection-graph resolution. The technique also provides a simplified completeness proof for semantic resolution. Some observations about subsumption and about link deletion are made. Link deletion is the basis for connection graphs. Subsumption plays an important role in most resolution-based inference systems. In some settings-for example, connection graphs in Negation Normal Form-both subsumption and link deletion can be quite tricky. Nevertheless, a completeness result that uses both is obtained in this setting.
-
completeness for linear regular Negation Normal Form inference systems
International Syposium on Methodologies for Intelligent Systems, 1997Co-Authors: Reiner Hähnle, Neil V. Murray, Erik RosenthalAbstract:Completeness proofs that generalize the Anderson- Bledsoe excess literal argument are developed for calculi other than resolution. A simple proof of the completeness of regular, connected tableaux for Formulas in conjunctive Normal Form (CNF) is presented. These techniques also provide completeness results for some inference mechanisms that do not rely on clause Form. In particular, the completeness of regular, connected tableaux for Formulas in Negation Normal Form (NNF), and the completeness of NC-resolution under a linear restriction, are established.
-
Fast Subsumption Checks Using Anti-Links
Journal of Automated Reasoning, 1997Co-Authors: Anavai Ramesh, Reiner Hähnle, Bernhard Beckert, Neil V. MurrayAbstract:The concept of anti-link is defined (an anti-link consists of two occurrences of the same literal in a Formula), and useful equivalence-preserving operations based on anti-links are introduced. These operations eliminate a potentially large number of subsumed paths in a Negation Normal Form Formula. Those anti-links that directly indicate the presence of subsumed paths are characterized. The operations have linear time complexity in the size of that part of the Formula containing the anti-link. The problem of removing all subsumed paths in an NNF Formula is shown to be NP-hard, even though such Formulas may be small relative to the size of their path sets. The general problem of determining whether there exists a pair of subsumed paths associated with an arbitrary anti-link is shown to be NP-complete. Additional techniques that generalize the concept of pure literals are introduced and are also shown to eliminate redundant subsumption checks. The effectiveness of these techniques is examined with respect to some benchmark examples from the literature.
Pierre Marquis - One of the best experts on this subject based on the ideXlab platform.
-
On the use of partially ordered decision graphs in knowledge compilation and quantified boolean Formulae
2013Co-Authors: Helene Fargier, Pierre MarquisAbstract:Decomposable Negation Normal Form Formulae (DNNFs) Form an interesting propositional fragment, both for efficiency and succinctness reasons. A famous subclass of the DNNF fragment is the OBDD fragment which offers many polytime queries and transFormations, including quantifier eliminations (under some ordering restrictions). Nevertheless, the decomposable AND nodes at work in OBDDs enable only sequential decisions: clusters of variables are never assigned “in parallel ” like in full DNNFs. This is an serious drawback since succinctness for the full DNNF fragment relies on such a “parallelization property”. This is why we suggest to go a step further, from (sequentially) ordered decision diagrams to (partially) ordered, decomposable decision graphs, in which any decomposable AND node is allowed, and not only assignment ones. We show that, like the OBDD fragment, such a new class offers many tractable queries and transFormations, including quantifier eliminations under some ordering restrictions. Furthermore, we show that this class is strictly more succinct than OBDD
-
on valued Negation Normal Form Formulas
International Joint Conference on Artificial Intelligence, 2007Co-Authors: Helene Fargier, Pierre MarquisAbstract:Subsets of the Negation Normal Form Formulas (NNFs) of propositional logic have received much attention in AI and proved as valuable representation languages for Boolean functions. In this paper, we present a new framework, called VNNF, for the representation of a much more general class of functions than just Boolean ones. This framework supports a larger family of queries and transFormations than in the NNF case, including optimization ones. As such, it encompasses a number of existing settings, e.g. NNFs, semiring CSPs, mixed CSPs, SLDDs, ADD, AADDs. We show how the properties imposed on NNFs to define more "tractable" fragments (decomposability, determinism, decision, read-once) can be extended to VNNFs, giving rise to subsets for which a number of queries and transFormations can be achieved in polynomial time.
-
IJCAI - On valued Negation Normal Form Formulas
2007Co-Authors: Helene Fargier, Pierre MarquisAbstract:Subsets of the Negation Normal Form Formulas (NNFs) of propositional logic have received much attention in AI and proved as valuable representation languages for Boolean functions. In this paper, we present a new framework, called VNNF, for the representation of a much more general class of functions than just Boolean ones. This framework supports a larger family of queries and transFormations than in the NNF case, including optimization ones. As such, it encompasses a number of existing settings, e.g. NNFs, semiring CSPs, mixed CSPs, SLDDs, ADD, AADDs. We show how the properties imposed on NNFs to define more "tractable" fragments (decomposability, determinism, decision, read-once) can be extended to VNNFs, giving rise to subsets for which a number of queries and transFormations can be achieved in polynomial time.
-
AAAI - On the use of partially ordered decision graphs for knowledge compilation and quantified Boolean Formulae
2006Co-Authors: Helene Fargier, Pierre MarquisAbstract:Decomposable Negation Normal Form Formulae (DNNFs) Form an interesting propositional fragment, both for efficiency and succinctness reasons. A famous subclass of the DNNF fragment is the OBDD fragment which offers many polytime queries and transFormations, including quantifier eliminations (under some ordering restrictions). Nevertheless, the decomposable AND nodes at work in OBDDs enable only sequential decisions: clusters of variables are never assigned "in parallel" like in full DNNFs. This is an serious drawback since succinctness for the full DNNF fragment relies on such a "parallelization property". This is why we suggest to go a step further, from (sequentially) ordered decision diagrams to (partially) ordered, decomposable decision graphs, in which any decomposable AND node is allowed, and not only assignment ones. We show that, like the OBDD fragment, such a new class offers many tractable queries and transFormations, including quantifier eliminations under some ordering restrictions. Furthermore, we show that this class is strictly more succinct than OBDD.
-
Complexity results for Quantified Boolean Formulae based on complete propositional languages
Journal on Satisfiability Boolean Modeling and Computation, 2006Co-Authors: Sylvie Coste-marquis, Daniel Le Berre, Florian Letombe, Pierre MarquisAbstract:Several propositional fragments have been considered so far as target languages for knowledge compilation and used for improving computational tasks from major AI areas (like inference, diagnosis and planning); among them are the ordered binary decision diagrams, prime implicates, prime implicants, \Formulae" in decomposable Negation Normal Form. On the other hand, the validity problem val(QPROPP S) for Quantied Boolean Formulae (QBF) has been acknowledged for the past few years as an important issue for AI, and many solvers have been designed. In this paper, the complexity of restrictions of the validity problem for QBF obtained by imposing the matrix of the input QBF to belong to propositional fragments used as target languages for compilation, is identied. It turns out that this problem remains hard (PSPACE-complete) even under severe restrictions on the matrix of the input. Nevertheless some tractable restrictions are pointed out.
