Quantified constraints and Quantified Boolean Formulae are typically much more difficult to reason with than classical constraints, because quantifier alternation makes the usual notion of solution inappropriate. As a consequence, basic properties of Constraint Satisfaction Problems (CSPs), such as consistency or substitutability, are not completely understood in the quantified case. These properties are important because they are the basis of most of the reasoning methods used to solve classical (existentially quantified) constraints, and it is desirable to benefit from similar reasoning methods in the resolution of quantified constraints. In this article, we show that most of the properties that are used by solvers for CSP can be generalized to quantified CSP. This requires a rethinking of a number of basic concepts; in particular, we propose a notion of outcome that generalizes the classical notion of solution and on which all definitions are based. We propose a systematic study of the relations which hold between these properties, as well as complexity results regarding the decision of these properties. Finally, and since these problems are typically intractable, we generalize the approach used in CSP and propose weaker, easier to check notions based on locality , which allow to detect these properties incompletely but in polynomial time.

Literature on Constraint Satisfaction exhibits the definition of several ``structural'' properties that can be possessed by CSPs, like (in)consistency, substitutability or interchangeability. Current tools for constraint solving typically detect such properties efficiently by means of incomplete yet effective algorithms, and use them to reduce the search space and boost search. In this paper, we provide a unifying framework encompassing most of the properties known so far, both in CSP and other fields' literature, and shed light on the semantical relationships among them. This gives a unified and comprehensive view of the topic, allows new, unknown, properties to emerge, and clarifies the computational complexity of the various detection problems. In particular, among the others, two new concepts, fixability and removability emerge, that come out to be the ideal characterisations of values that may be safely assigned or removed from a variable's domain, while preserving problem satisfiability. These two notions subsume a large number of known properties, including inconsistency, substitutability and others. Because of the computational intractability of all the property-detection problems, by following the CSP approach we then determine a number of relaxations which provide sufficient conditions for their tractability. In particular, we exploit forms of language restrictions and local reasoning.

Abstract The goal of this paper is to provide a strong integration between constraint modelling and relational DBMSs. To this end we propose extensions of standard query languages such as relational algebra and SQL, by adding constraint modelling capabilities to them. In particular, we propose non-deterministic extensions of both languages, which are specially suited for combinatorial problems. Non-determinism is introduced by means of a guessing operator, which declares a set of relations to have an arbitrary extension. This new operator results in languages with higher expressive power, able to express all problems in the complexity class NP. Some syntactical restrictions which make data complexity polynomial are shown. The effectiveness of both extensions is demonstrated by means of several examples. The current implementation, written in Java using local search techniques, is described.

In this paper, we define and study the k-approximating circuits. A circuit accepting a given set of inputs A is k-approximated by accepting inputs that lifter from one of A by at most k bits. We show that the existence of polynomial-size k-approximating circuits depends on the relation between k and the number of inputs.

Circumscription has been recognized as an important principle for knowledge representation and common-sense reasoning. The need for a circumscriptive formalism that allows for simple yet elegant modular problem representation has led Lifschitz (AIJ, 1995) to introduce nested abnormality theories (NATs) as a tool for modular knowledge representation, tailored for applying circumscription to minimize exceptional circumstances. Abstracting from this particular objective, we propose L CIRC , which is an extension of generic propositional circumscription by allowing propositional combinations and nesting of circumscriptive theories. As shown, NATs are naturally embedded into this language, and are in fact of equal expressive capability. We then analyze the complexity of L CIRC and NATs, and in particular the effect of nesting. The latter is found to be a source of complexity, which climbs the Polynomial Hierarchy as the nesting depth increases and reaches PSPACE-completeness in the general case. We also identify meaningful syntactic fragments of NATs which have lower complexity. In particular, we show that the generalization of Horn circumscription in the NAT framework remains coNP-complete, and that Horn NATs without fixed letters can be efficiently transformed into an equivalent Horn CNF, which implies polynomial solvability of principal reasoning tasks. Finally, we also study extensions of NATs and briefly address the complexity in the first-order case. Our results give insight into the “cost” of using L CIRC (respectively, NATs) as a host language for expressing other formalisms such as action theories, narratives, or spatial theories.

In Knowledge Compilation (KC) an intractable deduction problem KB ⊨ f is split into two phases: 1) KB is preprocessed, thus obtaining a data structure DKB; 2) the problem is efficiently solved using DKB and f. Our goal is to study KC in the context of relational databases: Both KB and f are represented as databases, and '⊨' is represented as a query Q in second-order logic. DKB is a database, to be synthesized from KB by means of an appropriate view. Q is rewritten, thus obtaining Qr. We show syntactic restrictions on Q implying that a polynomial-size DKB and a first-order Qr exist, which imply that phase 2 can be done in polynomial time. We also present classes of queries (in some sense complementary to the former ones) for which either no polynomial-size DKB or no first-order Qr exist (unless the PH collapses). Compilation to other complexity classes is also addressed.

We investigate the space efficiency of a Propositional Knowledge Representation (PKR) formalism. Intuitively, the space efficiency of a formalism F in representing a certain piece of knowledge A, is the size of the shortest formula of F that represents A. In this paper we assume that knowledge is either a set of propositional interpretations (models) or a set of propositional formulae (theorems). We provide a formal way of talking about the relative ability of PKR formalisms to compactly represent a set of models or a set of theorems. We introduce two new compactness measures, the corresponding classes, and show that the relative space efficiency of a PKR formalism in representing models/theorems is directly related to such classes. In particular, we consider formalisms for nonmonotonic reasoning, such as circumscription and default logic, as well as belief revision operators and the stable model semantics for logic programs with negation. One interesting result is that formalisms with the same time complexity do not necessarily belong to the same space efficiency class.

Local search is an emerging paradigm for combinatorial search which has recently been shown to be very effective for a large number of combinatorial problems. It is based on the idea of navigating the search space by iteratively stepping from one solution to one of its neighbors, which are obtained by applying a simple local change to it. In this paper we present LOCAL++, an object-oriented framework to be used as a general tool for the development and implementation of local search algorithms in C++. The framework comprises a hierarchy of abstract template classes, one for each local search technique taken into account (i.e. hill-climbing, simulated annealing and tabu search). Each class specifies and implements the invariant part of the algorithm built according to the technique, and is supposed to be specialized by a concrete class once a given search problem is considered, so as to implement the problem-dependent part of the algorithm. LOCAL++ comprises also a set of abstract classes for creating new techniques by combining different search techniques and different neighborhood relations. The architecture of LOCAL++ provides a principled modularization for the solution of combinatorial search problems, and helps the designer deriving a neat conceptual scheme of the application, thus facilitating the development and debugging phases. LOCAL++ proved to be flexible enough for the implementation of the algorithms solving various scheduling problems. Copyright © 2000 John Wiley & Sons, Ltd.

Research in nonmonotonic reasoning has focused largely on the idea of representing knowledge about the world via rules that are generally true but can be defeated. Even if relational databases are nowadays the main tool for storing very large sets of data, the approach of using nonmonotonic AI formalisms as relational database query languages has been investigated to a much smaller extent. In this work, we propose a novel application of Reiter's default logic by introducing a default query language (DQL) for finite relational databases, which is based on default rules. The main result of this paper is that DQL is as expressive as SO/sub /spl exist//spl forall// the existential-universal fragment of second-order logic. This result is not only of theoretical importance: We exhibit queries-which are useful in practice-that can be expressed with DQL and cannot with other query languages based on nonmonotonic logics such as DATALOG with negation under the stable model semantics. In particular, we show that DQL is well-suited for diagnostic reasoning.

Article Free Access Share on The size of a revised knowledge base Authors: Marco Cadoli Dipartimento di Informatica e Sistemistica, Università di Roma 'La Sapienza', via Salaria 113, I-00198, Roma, Italy Dipartimento di Informatica e Sistemistica, Università di Roma 'La Sapienza', via Salaria 113, I-00198, Roma, ItalyView Profile , Francesco M. Donini Dipartimento di Informatica e Sistemistica, Università di Roma 'La Sapienza', via Salaria 113, I-00198, Roma, Italy Dipartimento di Informatica e Sistemistica, Università di Roma 'La Sapienza', via Salaria 113, I-00198, Roma, ItalyView Profile , Paolo Liberatore Dipartimento di Informatica e Sistemistica, Università di Roma 'La Sapienza', via Salaria 113, I-00198, Roma, Italy Dipartimento di Informatica e Sistemistica, Università di Roma 'La Sapienza', via Salaria 113, I-00198, Roma, ItalyView Profile , Marco Schaerf Dipartimento di Informatica e Sistemistica, Università di Roma 'La Sapienza', via Salaria 113, I-00198, Roma, Italy Dipartimento di Informatica e Sistemistica, Università di Roma 'La Sapienza', via Salaria 113, I-00198, Roma, ItalyView Profile Authors Info & Claims PODS '95: Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsMay 1995 Pages 151–162https://doi.org/10.1145/212433.220205Published:22 May 1995Publication History 12citation198DownloadsMetricsTotal Citations12Total Downloads198Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We propose a technique for dealing with the high complexity of reasoning under propositional default logic and circumscription. The technique is based on the notion of approximation: A logical consequence relation is computed by means of sound and progressively “more complete” relations, as well as complete and progressively “more sound” ones. Both sequences generated in this way converge to the original consequence relation and are easier to compute. Moreover they are given a clear semantics based on multivalued logic. With this technique unsoundness and incompleteness are introduced in a controlled way and precisely characterized.

We propose a technique for dealing with the high complexity of reasoning under propositional default logic and circumscription. The technique is based on the notion of approximation: A logical consequence relation is computed by means of sound and pr