Home page of Marco Cadoli
% Time-stamp: "2003-06-18 12:31:31 Administrator"

Recent publications of Marco Cadoli

Publications: By publication media, in reverse chronological order

Publications: By subject.
Artificial Intelligence
Reasoning: Algorithms and complexity
[IntJourn4], [Book1], [IntJourn17], [IntJourn15], [IntJourn7], [IntJourn3], [IntJourn2], [IntJourn1], [IntConf21], [IntConf17], [IntConf8], [IntConf4], [IntConf3], [IntConf2], [IntConf1], [Invited2], [Invited1], [CEG03], [DoctoralThesis]
Knowledge compilation
[IntJourn11], [IntJourn10], [IntJourn8], [IntConf14], [IntJourn18], [IntConf10]
Approximate reasoning
[Book1], [IntJourn6], [IntJourn5], [IntConf7], [IntConf6], [IntConf5], [NatConf1], [DoctoralThesis]
Constraint programming and constraint modeling languages
[IntJourn19], [IntConf23], [IntConf22], [IntConf18], [IntConf20], [Invited4], [Cad02], [CM03], [CS02]
Quantified Boolean Formulae: Solvers and experiments
[BookChap1], [IntJourn20], [IntConf16], [NatConf3],
Agents and negotiation
[IntConf25]
Abstraction
[IntJourn13]
Data and Knowledge Bases
Query languages
[IntJourn12], [IntConf15], [IntJourn9], [IntConf9]
Query rewriting
[IntConf24]
Revision and update
[IntJourn14], [IntConf12]
Software Engineering
Programming methodologies and techniques
[Book3], [Book2], [BookChap2]
Software development tools
[BookChap3], [IntJourn16], [IntConf19]
Theoretical Computer Science
Preprocessing and space efficiency
[IntJourn21], [IntConf13], [IntJourn10], [IntConf11], [Invited3]
Computational complexity
[NatConf2], [CDLS02]

Copyright notice
The documents available from this site are provided as a means to ensure timely dissemination of technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder (Springer-Verlag for works appeared in the LNCS series, ACM-SIAM, IEEE, etc.). Permission to make digital or hard copies of part or all of these works for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage. The electronic version of some of the works available from this site may differ from the definitive published version. Copyright of works submitted for publication may be transferred without further notice and this version may no longer be accessible.

Bibliography

Books

Book3
M. Cadoli, M. Lenzerini, E. Panizzi, and A. Schaerf.
Esercizi di progettazione di programmi in C++.
Città Studi Edizioni di UTET Libreria, Torino, 1998.
ISBN 88-251-7727-3.
In Italian.

Book2
M. Cadoli, M. Lenzerini, P. Naggar, and A. Schaerf.
Fondamenti della progettazione dei programmi. Princìpi, tecniche e loro applicazioni in C++.
Città Studi Edizioni di UTET Libreria, Torino, 1997.
ISBN 88-251-7161-7.
In Italian.

Book1
M. Cadoli.
Tractable Reasoning in Artificial Intelligence.
Number 941 in Lecture Notes In Artificial Intelligence. Springer, Berlin, Heidelberg, New York, 1995.
ISBN 3-540-60058-2.

Book chapters

BookChap3
Daniele Ballarini, Marco Cadoli, Matteo Gaeta, Toni Mancini, Massimo Mecella, Pierluigi Ritrovato, and Giuseppe Santucci.
Cooperative Software Development in GENESIS: Requirements, Conceptual Model and Architecture.
In Aniello Cimitile, Andrea De Lucia, and Harald Gall, editors, TBA. Franco Angeli, 2003.
To appear.

BookChap2
M. Cadoli, G. De Giacomo, and M. Schaerf.
Programmazione orientata agli oggetti e Java.
In D. Cioffi and R. Falzone, editors, Manuale di Informatica, IV edizione. Calderini, Bologna, 2002.
ISBN 88-506-4869-3.
In Italian.

BookChap1
Marco Cadoli, Marco Schaerf, Andrea Giovanardi, and Massimo Giovanardi.
An algorithm to evaluate quantified boolean formulae and its experimental evaluation.
In Ian Gent, Hans van Maaren, and Toby Walsh, editors, SAT2000 - Highlights of Satisfiability Research in the Year 2000, pages 485-521. IOS Press, 2000.
Appears also on Journal of Automated Reasoning, special issue on SAT2000.

Journal articles

International journals

IntJourn21
Marco Cadoli, Francesco M. Donini, Paolo Liberatore, and Marco Schaerf.
Preprocessing of intractable problems.
Information and Computation 176(2):89-120, 2002.

IntJourn20
Marco Cadoli, Marco Schaerf, Andrea Giovanardi, and Massimo Giovanardi.
An algorithm to evaluate quantified boolean formulae and its experimental evaluation.
Journal of Automated Reasoning , 28:101-142, 2002.

IntJourn19
M. Cadoli, G. Ianni, L. Palopoli, A. Schaerf, and D. Vasile.
NP-SPEC: An executable specification language for solving all problems in NP.
Computer Languages 26:165-195, 2000.

IntJourn18
M.  Cadoli, F. M. Donini, P.  Liberatore, and M.  Schaerf.
Space efficiency of propositional knowledge representation formalisms.
Journal of Artificial Intelligence Research 13:1-31, 2000.

IntJourn17
M. Cadoli and F. Scarcello.
Semantical and computational aspects of Horn approximations.
Artificial Intelligence , 119(1-2):1-17, 2000.

IntJourn16
A.  Schaerf, M.  Cadoli, and M.  Lenzerini.
LOCAL++: A C++ framework for local search algorithms.
Software --- Practice and Experience 30(3):233-257, 2000.

IntJourn15
M.  Cadoli, L.  Palopoli, and F.  Scarcello.
Propositional lower bounds: Algorithms and complexity.
Annals of Mathematics and Artificial Intelligence 27:129-148, 1999.

IntJourn14
M.  Cadoli, F. M. Donini, P.  Liberatore, and M.  Schaerf.
The size of a revised knowledge base.
Artificial Intelligence , 115(1):25-64, 1999.

IntJourn13
R. W. Weyhrauch, M. Cadoli, and C. L. Talcott.
Using abstract resources to control reasoning.
Journal of Logic, Language and Information 7(1):77-101, 1998.

IntJourn12
M. Cadoli and L. Palopoli.
Circumscribing Datalog: expressive power and complexity.
Theoretical Computer Science 193:215-244, 1998.

IntJourn11
M. Cadoli and F. M. Donini.
A survey on knowledge compilation.
AI Communications--The European Journal for Artificial Intelligence 10:137-150, 1997.

IntJourn10
M. Cadoli, F. M. Donini, M. Schaerf, and R. Silvestri.
On compact representations of propositional circumscription.
Theoretical Computer Science 182:183-202, 1997.

IntJourn9
M. Cadoli, T. Eiter, and G. Gottlob.
Default logic as a query language.
IEEE Transactions on Knowledge and Data Engineering 9(3):448-463, May/June 1997.

IntJourn8
M. Cadoli, F.M. Donini, and M. Schaerf.
Is intractability of non-monotonic reasoning a real drawback?
Artificial Intelligence , 88:215-251, 1996.

IntJourn7
M. Cadoli and M. Schaerf.
On the complexity of entailment in propositional multivalued logics.
Annals of Mathematics and Artificial Intelligence 18:29-50, 1996.

IntJourn6
M. Schaerf and M. Cadoli.
Tractable reasoning via approximation.
Artificial Intelligence , 74:249-310, 1995.

IntJourn5
M. Cadoli and M. Schaerf.
Approximate inference in default reasoning and circumscription.
Fundamenta Informaticae , 23:123-143, 1995.

IntJourn4
M. Cadoli and M. Lenzerini.
The complexity of propositional closed world reasoning and circumscription.
Journal of Computer and System Sciences , 48:255-310, 1994.

IntJourn3
M. Cadoli and M. Schaerf.
A survey of complexity results for non-monotonic logics.
Journal of Logic Programming , 17:127-160, 1993.

IntJourn2
M. Cadoli.
The complexity of model checking for circumscriptive formulae.
Information Processing Letters , 44:113-118, 1992.

IntJourn1
M. Cadoli, T. Eiter, and G. Gottlob.
An efficient method for eliminating varying predicates from a circumscription.
Artificial Intelligence , 54:397-410, 1992.

Italian journals

NatJourn3
M. Cadoli, M. Schaerf, and M. Giovanardi.
Evaluation of quantified boolean formulae on Sigma-p-k- and PSPACE-complete instances.
AI*IA Notizie, 13(1):41-43, marzo 2000.

NatJourn2
M. Cadoli.
Due metodi per il ragionamento trattabile in Intelligenza Artificiale: restrizione del linguaggio e approssimazione delle teorie.
AI*IA Notizie, 6(3):16-41, settembre 1993.

NatJourn1
M. Cadoli.
La complessità computazionale del ragionamento di mondo chiuso.
AI*IA Notizie, 3(3):8-23, settembre 1990.

Conference papers

International conferences

IntConf25
Marco Cadoli.
Proposal-based negotiation in convex regions.
In Proceedings of the Seventh International Workshop on Cooperative Information Agents (CIA 2003), Lecture Notes in Computer Science. Springer, 2003.

IntConf24
Marco Cadoli and Toni Mancini.
Knowledge compilation = Query rewriting + View synthesis.
In Proceedings of the Twentyfirst ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS 2002), pages 199-208. ACM Press and Addison Wesley, 2002.

IntConf23
Marco Cadoli and Toni Mancini.
Combining Relational Algebra, SQL, and Constraint Programming.
In Proceeding of the Fourth International Workshop on Frontiers of Combining Systems (FroCoS 2002), volume 2309 of Lecture Notes in Artificial Intelligence, pages 147-161. Springer, 2002.

IntConf22
Marco Cadoli.
The expressive power of binary linear programming.
In Proceedings of the Seventh International Conference on Principles and Practice of Constraint Programming (CP 2001), Lecture Notes in Computer Science. Springer-Verlag, 2001.

IntConf21
M. Cadoli, T. Eiter, and G. Gottlob.
Complexity of nested circumscription and abnormality theories.
In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI 2001), pages 169-174, 2001.

IntConf20
M. Cadoli and Andrea Schaerf.
Compiling problem specifications into SAT.
In Proceedings of the European Symposium On Programming (ESOP 2001), volume 2028 of Lecture Notes in Computer Science, pages 387-401. Springer-Verlag, 2001.

IntConf19
A.  Schaerf, M.  Lenzerini, and M.  Cadoli.
LOCAL++: A C++ framework for combinatorial search problems.
In Proceedings of the Twentyninth International Conference on Technology of Object-Oriented Languages and Systems (TOOLS-EUROPE'99), pages 152-161, Nancy, France, 1999.

IntConf18
M. Cadoli, L. Palopoli, A. Schaerf, and D. Vasile.
NP-SPEC: An executable specification language for solving all problems in NP.
In Proceedings of the First International Workshop on Practical Aspects of Declarative Languages (PADL'99), number 1551 in Lecture Notes In Artificial Intelligence. Springer-Verlag, 1999.

IntConf17
M. Cadoli, L. Palopoli, and F. Scarcello.
Propositional lower bounds: Generalization and algorithms.
In Proceedings of the Sixth European Workshop on Logics in Artificial Intelligence (JELIA-98), number 1489 in Lecture Notes In Artificial Intelligence, pages 355-367. Springer-Verlag, 1998.

IntConf16
M. Cadoli, A. Giovanardi, and M. Schaerf.
An algorithm to evaluate quantified boolean formulae.
In Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-98), pages 262-267, 1998.

IntConf15
M. Cadoli, L. Palopoli, and M. Lenzerini.
Datalog and description logics: Expressive power.
In Proceedings of the Sixth International Workshop on Database Programming Languages (DBPL-97), number 1369 in Lecture Notes in Computer Science, pages 281-298. Springer-Verlag, 1998.

IntConf14
M. Cadoli, F.M. Donini, P. Liberatore, and M. Schaerf.
Comparing space efficiency of propositional knowledge representation formalisms.
In Proceedings of the Fifth International Conference on the Principles of Knowledge Representation and Reasoning (KR-96), pages 364-373, 1996.

IntConf13
M. Cadoli, F. M. Donini, P. Liberatore, and M. Schaerf.
Feasibility and unfeasibility of off-line processing.
In Proceedings of the Fourth Israeli Symposium on Theory of Computing and Systems (ISTCS-96), pages 100-109. IEEE Computer Society, 1996.

IntConf12
M. Cadoli, F.M. Donini, P. Liberatore, and M. Schaerf.
The size of a revised knowledge base.
In Proceedings of the Fourteenth ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS-95), pages 151-162, 1995.

IntConf11
M. Cadoli, F.M. Donini, and M. Schaerf.
On compact representations of propositional circumscription.
In Proceedings of the Twelfth Symposium on Theoretical Aspects of Computer Science (STACS-95), number 900 in Lecture Notes In Computer Science, pages 205-216. Springer-Verlag, 1995.

IntConf10
M. Cadoli, F.M. Donini, and M. Schaerf.
Is intractability of non-monotonic reasoning a real drawback?
In Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI-94), pages 946-951. MIT press, 1994.

IntConf9
M. Cadoli, T. Eiter, and G. Gottlob.
Default logic as a query language.
In Proceedings of the Fourth International Conference on the Principles of Knowledge Representation and Reasoning (KR-94), pages 99-108. Morgan Kaufmann Publisher, 1994.

IntConf8
M. Cadoli.
Semantical and computational aspects of Horn approximations.
In Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (IJCAI-93), pages 39-44, August 1993.

IntConf7
M. Cadoli and M. Schaerf.
Approximation in concept description languages.
In Proceedings of the Third International Conference on the Principles of Knowledge Representation and Reasoning (KR-92), pages 330-341. Morgan Kaufmann Publishers, October 1992.

IntConf6
M. Cadoli and M. Schaerf.
Approximate inference in default reasoning and circumscription.
In Proceedings of the Tenth European Conference on Artificial Intelligence (ECAI-92), pages 319-323. John Wiley, August 1992.

IntConf5
M. Cadoli and M. Schaerf.
Approximate reasoning and non-omniscient agents.
In Proceedings of the Fourth Conference on Theoretical Aspects of Reasoning about Knowledge (TARK-92), pages 169-183. Morgan Kaufmann Publisher, 1992.

IntConf4
M. Cadoli, M. Lenzerini, D. Nardi, and F. Pirri.
Circumscription and nonmonotonic inheritance.
In Proceedings of the 1st Pacific Rim Conference on Artificial Intelligence (PRICAI-90), pages 760-765. Japanese Society for Artificial Intelligence, November 1990.

IntConf3
M. Cadoli.
Adding failure priority knowledge to Reiter's diagnosis.
In Proceedings of the 3rd International Symposium on Artificial Intelligence (SIIA-9O), pages 90-95. Editorial Limusa, October 1990.

IntConf2
M. Cadoli, F.M. Donini, and M. Schaerf.
Closed world reasoning in hybrid systems.
In Proceedings of the 5th International Symposium on Methodologies for Intelligent Systems (ISMIS-90), pages 474-481. North Holland, 1990.

IntConf1
M. Cadoli and M. Lenzerini.
The complexity of closed world reasoning and circumscription.
In Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI-90), pages 550-555. MIT press, July 1990.

Invited talks

Invited4
M.  Cadoli.
Using LPNMR for problem specification and code generation.
In Proceedings of the Fifth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'99), number 1730 in Lecture Notes in Artificial Intelligence, page 372. Springer-Verlag, 1999.

Invited3
M. Cadoli, F.M. Donini, P. Liberatore, and M. Schaerf.
Comparing space efficiency of propositional knowledge representation formalisms.
In Proceedings of the FLoC 1999 Workshop on Complexity-theoretic and Recursion-theoretic methods in Databases, Artificial Intelligence and Finite Model Theory, pages 13-22, 1999.

Invited2
M. Cadoli.
Panel on ``Knowledge Compilation and Approximation'': Terminology, Questions, References.
Fourth International Symposium on Artificial Intelligence and Mathematics, 1996.

Invited1
M. Cadoli.
A survey of complexity results for planning.
In Proceedings of the Italian Planning Workshop (IPW-93), pages 131-145, 1993. ISBN 88-85059-01-5.

Italian conferences

NatConf3
M. Cadoli, A. Giovanardi, and M. Schaerf.
Experimental analysis of the computational cost of evaluating quantified boolean formulae.
In Proceedings of the Fifth Conference of the Italian Association for Artificial Intelligence (AI*IA-97), number 1321 in Lecture Notes In Artificial Intelligence, pages 207-218. Springer-Verlag, 1997.

NatConf2
M. Cadoli.
On the complexity of model finding for nonmonotonic propositional logics.
In Proceedings of the Fourth Italian Conference on Theoretical Computer Science, pages 125-139. World Scientific Publishing Co., October 1992.

NatConf1
M. Cadoli and M. Schaerf.
Approximate entailment.
In Trends in Artificial Intelligence: Proceedings of the 2nd Conference of the Italian Association for Artificial Intelligence, number 549 in Lecture Notes In Artificial Intelligence, pages 68-77. Springer-Verlag, 1991.

Technical reports, submitted papers, etc.

CDLS02
Marco Cadoli, Francesco M. Donini, Paolo Liberatore, and Marco Schaerf.
k-approximating circuits.
Technical Report TR02-067, Electronic Colloquium on Computational Complexity, 2002.

Cad02
Marco Cadoli.
The expressive power of binary linear programming.
Submitted to an international journal, 2002.

CEG03
Marco Cadoli, Thomas Eiter, and Georg Gottlob.
Complexity of nested circumscription and abnormality theories.
Submitted to an international journal.

CM03
Marco Cadoli and Toni Mancini.
Towards automated reformulation of specifications.
Submitted to an international conference, 2003.

CS02
Marco Cadoli and Andrea Schaerf.
Compiling problem specifications into SAT.
Submitted to an international journal, 2002.

Doctoral thesis

DoctoralThesis
M. Cadoli.
Two methods for tractable reasoning in artificial intelligence: Language restriction and theory approximation.
Doctoral thesis, July 1993. Number V-93-1 in the collection. 247 pages.


Marco Cadoli 2003-06-18