Bibliography

1

R. Ben-Eliyahu and R. Dechter.
Default logic, propositional logic and constraints.
In Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI'91), pages 379-385, 1991.

2

R. Ben-Eliyahu and R. Dechter.
Propositional semantics for disjunctive logic programs.
Annals of Mathematics and Artificial Intelligence, 12:53-87, 1994.

3

R. Boppana and M. Sipser.
The complexity of finite functions.
In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A, chapter 14, pages 757-804. Elsevier Science Publishers (North-Holland), Amsterdam, 1990.

4

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

5

M. Cadoli, F. 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.

6

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 Press, 1996.
URL = FTP://FTP.DIS.UNIROMA1.IT/PUB/AI/PAPERS/CADO-ETAL-96.PS.GZ.

7

M. Cadoli, F. M. Donini, P. Liberatore, and M. Schaerf.
Preprocessing of intractable problems.
Technical Report DIS 24-97, Dipartimento di Informatica e Sistemistica, Università di Roma ``La Sapienza'', November 1997.
URL = HTTP://FTP.DIS.UNIROMA1.IT/PUB/AI/PAPERS/CADO-ETAL-97-D-REVISED.PS.GZ.

8

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

9

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), pages 205-216, 1995.
Extended version as RAP.14.95 DIS, Univ. of Roma ``La Sapienza'', July 1995.

10

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

11

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

12

S. A. Cook.
The complexity of theorem-proving procedures.
In Proceedings of the Third ACM Symposium on Theory of Computing (STOC'71), pages 151-158, 1971.

13

T. Eiter and G. Gottlob.
On the complexity of propositional knowledge base revision, updates and counterfactuals.
Artificial Intelligence, 57:227-270, 1992.

14

T. Eiter and G. Gottlob.
Propositional circumscription and extended closed world reasoning are $\Pi^p_2$-complete.
Theoretical Computer Science, 114:231-245, 1993.

15

D. V. Etherington.
Reasoning with incomplete information.
Morgan Kaufmann, Los Altos, Los Altos, CA, 1987.

16

R. Fagin, J. D. Ullman, and M. Y. Vardi.
On the semantics of updates in databases.
In Proceedings of the Second ACM SIGACT SIGMOD Symposium on Principles of Database Systems (PODS'83), pages 352-365, 1983.

17

M. R. Garey and D. S. Johnson.
Computers and Intractability: A Guide to the Theory of NP-Completeness.
W.H. Freeman and Company, San Francisco, Ca, 1979.

18

M. Gelfond and V. Lifschitz.
The stable model semantics for logic programming.
In Proceedings of the Fifth Logic Programming Symposium, pages 1070-1080. The MIT Press, 1988.

19

M. Gelfond, H. Przymusinska, and T. Przymusinsky.
On the relationship between circumscription and negation as failure.
Artificial Intelligence, 38:49-73, 1989.

20

M. L. Ginsberg.
Conterfactuals.
Artificial Intelligence, 30:35-79, 1986.

21

G. Gogic, H. A. Kautz, C. Papadimitriou, and B. Selman.
The comparative linguistics of knowledge representation.
In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI'95), pages 862-869, 1995.

22

G. Gottlob.
Complexity results for nonmonotonic logics.
Journal of Logic and Computation, 2:397-425, 1992.

23

G. Gottlob.
Translating default logic into standard autoepistemic logic.
Journal of the ACM, 42:711-740, 1995.

24

T. Imielinski.
Results on translating defaults to circumscription.
Artificial Intelligence, 32:131-146, 1987.

25

T. Janhunen.
On the intertranslatability of autoepistemic, default and priority logics, and parallel circumscription.
In Proceedings of the Sixth European Workshop on Logics in Artificial Intelligence (JELIA'98), number 1489 in Lecture Notes in Artificial Intelligence, pages 216-232. Springer-Verlag, 1998.

26

D. S. Johnson.
A catalog of complexity classes.
In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A, chapter 2, pages 67-161. Elsevier Science Publishers (North-Holland), Amsterdam, 1990.

27

R. M. Karp and R. J. Lipton.
Some connections between non-uniform and uniform complexity classes.
In Proceedings of the Twelfth ACM Symposium on Theory of Computing (STOC'80), pages 302-309, 1980.

28

H. A. Kautz, M. J. Kearns, and B. Selman.
Horn approximations of empirical data.
Artificial Intelligence, 74:129-145, 1995.

29

H. A. Kautz and B. Selman.
Hard problems for simple default logics.
Artificial Intelligence, 49:243-279, 1991.

30

H. A. Kautz and B. Selman.
Forming concepts for fast inference.
In Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI'92), pages 786-793, 1992.

31

R. Khardon and D. Roth.
Reasoning with models.
Artificial Intelligence, 87:187-213, 1996.

32

R. Khardon and D. Roth.
Defaults and relevance in model-based reasoning.
Artificial Intelligence, 97:169-193, 1997.

33

J. Köbler and O. Watanabe.
New collapse consequences of NP having small circuits.
SIAM Journal on Computing, 28(1):311-324, 1998.

34

P. G. Kolaitis and C. H. Papadimitriou.
Some computational aspects of circumscription.
Journal of the ACM, 37(1):1-14, 1990.

35

P. Liberatore.
Compact representation of revision of Horn clauses.
In Xin Yao, editor, Proceedings of the Eighth Australian Joint Artificial Intelligence Conference (AI'95), pages 347-354. World Scientific, 1995.

36

P. Liberatore.
Compilation of intractable problems and its application to Artificial Intelligence.
PhD thesis, Dipartimento di Informatica e Sistemistica, Università di Roma ``La Sapienza'', 1998.
URL = ftp://ftp.dis.uniroma1.it/pub/AI/papers/libe-98-c.ps.gz.

37

P. Liberatore and M. Schaerf.
The complexity of model checking for belief revision and update.
In Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI'96), pages 556-561, 1996.

38

P. Liberatore and M. Schaerf.
The complexity of model checking for propositional default logics.
In Proceedings of the Thirteenth European Conference on Artificial Intelligence (ECAI'98), pages 18-22, 1998.

39

P. Liberatore and M. Schaerf.
The compactness of belief revision and update operators.
Technical report, Dipartimento di Informatica e Sistemistica, Università di Roma ``La Sapienza'', 2000.

40

W. Marek and M. Truszczynski.
Autoepistemic logic.
Journal of the ACM, 38(3):588-619, 1991.

41

J. McCarthy.
Circumscription - A form of non-monotonic reasoning.
Artificial Intelligence, 13:27-39, 1980.

42

J. Minker.
On indefinite databases and the closed world assumption.
In Proceedings of the Sixth International Conference on Automated Deduction (CADE'82), pages 292-308, 1982.

43

Y. Moses and M. Tennenholtz.
Off-line reasoning for on-line efficiency: knowledge bases.
Artificial Intelligence, 83:229-239, 1996.

44

B. Nebel.
How hard is it to revise a belief base?
In D. Dubois and H. Prade, editors, Belief Change - Handbook of Defeasible Reasoning and Uncertainty Management Systems, Vol. 3. Kluwer Academic, 1998.

45

R. Reiter.
A logic for default reasoning.
Artificial Intelligence, 13:81-132, 1980.

46

J. S. Schlipf.
Decidability and definability with circumscription.
Annals of Pure and Applied Logic, 35:173-191, 1987.

47

J. S. Schlipf.
A survey of complexity and undecidability results for logic programming.
Annals of Mathematics and Artificial Intelligence, 15:257-288, 1995.

48

B. Selman and H. A. Kautz.
Knowledge compilation and theory approximation.
Journal of the ACM, 43:193-224, 1996.

49

L. J. Stockmeyer.
The polynomial-time hierarchy.
Theoretical Computer Science, 3:1-22, 1976.

50

M. Winslett.
Sometimes updates are circumscription.
In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (IJCAI'89), pages 859-863, 1989.

51

M. Winslett.
Updating Logical Databases.
Cambridge University Press, 1990.

52

C. K. Yap.
Some consequences of non-uniform conditions on uniform classes.
Theoretical Computer Science, 26:287-300, 1983.