Search

Your search keyword '"Cadoli, Marco"' showing total 167 results
Start Over Author "Cadoli, Marco"
167 results on '"Cadoli, Marco"'

1. A Unifying Framework for Structural Properties of CSPs: Definitions, Complexity, Tractability

Author

Bordeaux, Lucas, Cadoli, Marco, and Mancini, Toni

Subjects
Computer Science - Artificial Intelligence, Computer Science - Logic in Computer Science
Abstract

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 variables 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.

Published
2014
Full Text
View/download PDF

2. Generalizing Consistency and other Constraint Properties to Quantified Constraints

Author

Bordeaux, Lucas, Cadoli, Marco, and Mancini, Toni

Subjects
Computer Science - Logic in Computer Science, Computer Science - Artificial Intelligence, I.2.8
Abstract

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 (CSP), 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 one would like to benefit from similar reasoning methods in the resolution of quantified constraints. In this paper, we show that most of the properties that are used by solvers for CSP can be generalized to quantified CSP. This requires a re-thinking 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.

Published
2007

3. Combining Relational Algebra, SQL, Constraint Modelling, and Local Search

Author

Cadoli, Marco and Mancini, Toni

Subjects
Computer Science - Artificial Intelligence, Computer Science - Logic in Computer Science
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. To appear in Theory and Practice of Logic Programming (TPLP), Comment: 30 pages, 5 figures

Published
2006
Full Text
View/download PDF

4. Complexity of Nested Circumscription and Nested Abnormality Theories

Author

Cadoli, Marco, Eiter, Thomas, and Gottlob, Georg

Subjects
Computer Science - Artificial Intelligence, Computer Science - Computational Complexity, Computer Science - Logic in Computer Science, I.2.3, I.2.4, F4.1, F.2.2
Abstract

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} (resp. NATs) as a host language for expressing other formalisms such as action theories, narratives, or spatial theories., Comment: A preliminary abstract of this paper appeared in Proc. Seventeenth International Joint Conference on Artificial Intelligence (IJCAI-01), pages 169--174. Morgan Kaufmann, 2001

Published
2002

6. SAT as an Effective Solving Technology for Constraint Problems

Author

Cadoli, Marco, Mancini, Toni, Patrizi, Fabio, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Esposito, Floriana, editor, Raś, Zbigniew W., editor, Malerba, Donato, editor, and Semeraro, Giovanni, editor

Published
2006
Full Text
View/download PDF

7. Partial Solutions with Unique Completion

Author

Cadoli, Marco, Schaerf, Marco, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Stock, Oliviero, editor, and Schaerf, Marco, editor

Published
2006
Full Text
View/download PDF

8. On the Separability of Subproblems in Benders Decompositions

Author

Cadoli, Marco, Patrizi, Fabio, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Beck, J. Christopher, editor, and Smith, Barbara M., editor

Published
2006
Full Text
View/download PDF

9. Exploiting Fixable, Removable, and Implied Values in Constraint Satisfaction Problems

Author

Bordeaux, Lucas, Cadoli, Marco, Mancini, Toni, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Baader, Franz, editor, and Voronkov, Andrei, editor

Published
2005
Full Text
View/download PDF

10. Detecting and Breaking Symmetries by Reasoning on Problem Specifications

Author

Mancini, Toni, Cadoli, Marco, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Zucker, Jean-Daniel, editor, and Saitta, Lorenza, editor

Published
2005
Full Text
View/download PDF

11. Using a Theorem Prover for Reasoning on Constraint Problems

Author

Cadoli, Marco, Mancini, Toni, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Bandini, Stefania, editor, and Manzoni, Sara, editor

Published
2005
Full Text
View/download PDF

12. Exploiting Functional Dependencies in Declarative Problem Specifications

Author

Cadoli, Marco, Mancini, Toni, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Alferes, Jóse Júlio, editor, and Leite, João, editor

Published
2004
Full Text
View/download PDF

13. Proposal-Based Negotiation in Convex Regions

Author

Cadoli, Marco, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Klusch, Matthias, editor, Omicini, Andrea, editor, Ossowski, Sascha, editor, and Laamanen, Heimo, editor

Published
2003
Full Text
View/download PDF

17. Propositional Lower Bounds: Generalization and Algorithms

Author

Cadoli, Marco, Palopoli, Luigi, Scarcello, Francesco, Goos, G., editor, Hartmanis, J., editor, van Leeuwen, J., editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Dix, Jürgen, editor, del Cerro, Luís Fariñas, editor, and Furbach, Ulrich, editor

Published
1998
Full Text
View/download PDF

21. Approximate entailment

Author

Cadoli, Marco, Schaerf, Marco, Siekmann, Jörg, editor, Goos, G., editor, Hartmanis, J., editor, Ardizzone, Edoardo, editor, Gaglio, Salvatore, editor, and Sorbello, Filippo, editor

Published
1991
Full Text
View/download PDF

26. k-approximating circuits

Author

Cadoli, Marco, Donini, Francesco M., Liberatore, Paolo, and Schaerf, Marco

Subjects
Hamming code -- Usage, Approximation theory -- Usage
Published
2006

30. NP-SPEC: an executable specification language for solving all problems in NP

Author

Cadoli, Marco, Ianni, Giovambattista, Palopoli, Luigi, Schaerf, Andrea, and Vasile, Domenico

Subjects
Logic programming -- Methods, Computers
Abstract

NP-SPEC, a logic-based specification language, is extrapolated from DATALOG via limited use of second-order predicates. A prototype is presented that compiles to PROLOG code.

Published
2000

39. Default logic as a query language

Author

Cadoli, Marco, Eiter, Thomas, and Gottlob, Georg

Subjects
Relational databases -- Research, Databases -- Research, Logic devices -- Research, Business, Computers, Electronics, Electronics and electrical industries
Abstract

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 Al 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.[exists][for every]], 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. Index Terms - Nonmonotonic reasoning, default logic, query languages, relational databases, expressive power.

Published
1997

Catalog

Books, media, physical & digital resources
See catalog results