\begin{thebibliography}{10}

\bibitem{bene-dech-91}
R.~Ben-Eliyahu and R.~Dechter.
\newblock Default logic, propositional logic and constraints.
\newblock In {\em Proceedings of the Ninth National Conference on Artificial
  Intelligence (AAAI'91)}, pages 379--385, 1991.

\bibitem{bene-dech-94}
R.~Ben-Eliyahu and R.~Dechter.
\newblock Propositional semantics for disjunctive logic programs.
\newblock {\em Annals of Mathematics and Artificial Intelligence}, 12:53--87,
  1994.

\bibitem{bopp-sips-90}
R.~Boppana and M.~Sipser.
\newblock The complexity of finite functions.
\newblock In J.~van Leeuwen, editor, {\em Handbook of Theoretical Computer
  Science}, volume~A, chapter~14, pages 757--804. Elsevier Science Publishers
  (North-Holland), Amsterdam, 1990.

\bibitem{cado-92-b}
M.~Cadoli.
\newblock The complexity of model checking for circumscriptive formulae.
\newblock {\em Information Processing Letters}, 44:113--118, 1992.

\bibitem{cado-etal-96-b}
M.~Cadoli, F.~Donini, P.~Liberatore, and M.~Schaerf.
\newblock Comparing space efficiency of propositional knowledge representation
  formalisms.
\newblock In {\em Proceedings of the Fifth International Conference on the
  Principles of Knowledge Representation and Reasoning (KR'96)}, pages
  364--373, 1996.

\bibitem{cado-etal-96}
M.~Cadoli, F.~M. Donini, P.~Liberatore, and M.~Schaerf.
\newblock Feasibility and unfeasibility of off-line processing.
\newblock In {\em Proceedings of the Fourth Israeli Symposium on Theory of
  Computing and Systems (ISTCS'96)}, pages 100--109. {IEEE} Computer Society
  Press, 1996.
\newblock {\sc url = \tt
  ftp://ftp.dis.uniroma1.it/PUB/AI/papers/cado-etal-96.ps.gz}.

\bibitem{cado-etal-97-d}
M.~Cadoli, F.~M. Donini, P.~Liberatore, and M.~Schaerf.
\newblock Preprocessing of intractable problems.
\newblock Technical Report DIS 24-97, Dipartimento di Informatica e
  Sistemistica, Universit{\`a} di Roma ``La Sapienza'', November 1997.
\newblock {\sc url = \tt
  http://ftp.dis.uniroma1.it/PUB/AI/papers/cado-etal-97-d-REVISED.ps.gz}.

\bibitem{cado-etal-99}
M.~Cadoli, F.~M. Donini, P.~Liberatore, and M.~Schaerf.
\newblock The size of a revised knowledge base.
\newblock {\em Artificial Intelligence}, 115(1):25--64, 1999.

\bibitem{cado-doni-scha-95}
M.~Cadoli, F.~M. Donini, and M.~Schaerf.
\newblock On compact representations of propositional circumscription.
\newblock In {\em Proceedings of the Twelfth Symposium on Theoretical Aspects
  of Computer Science (STACS'95)}, pages 205--216, 1995.
\newblock Extended version as RAP.14.95 DIS, Univ. of Roma ``La Sapienza'',
  July 1995.

\bibitem{cado-doni-scha-96}
M.~Cadoli, F.~M. Donini, and M.~Schaerf.
\newblock Is intractability of non-monotonic reasoning a real drawback?
\newblock {\em Artificial Intelligence}, 88(1--2):215--251, 1996.

\bibitem{cado-etal-97-c}
M.~Cadoli, F.~M. Donini, M.~Schaerf, and R.~Silvestri.
\newblock On compact representations of propositional circumscription.
\newblock {\em Theoretical Computer Science}, 182:183--202, 1997.

\bibitem{cook-71}
S.~A. Cook.
\newblock The complexity of theorem-proving procedures.
\newblock In {\em Proceedings of the Third ACM Symposium on Theory of Computing
  (STOC'71)}, pages 151--158, 1971.

\bibitem{eite-gott-91-b}
T.~Eiter and G.~Gottlob.
\newblock On the complexity of propositional knowledge base revision, updates
  and counterfactuals.
\newblock {\em Artificial Intelligence}, 57:227--270, 1992.

\bibitem{eite-gott-93-b}
T.~Eiter and G.~Gottlob.
\newblock Propositional circumscription and extended closed world reasoning are
  {$\Pi^p_2$}-complete.
\newblock {\em Theoretical Computer Science}, 114:231--245, 1993.

\bibitem{ethe-87-a}
D.~V. Etherington.
\newblock {\em Reasoning with incomplete information}.
\newblock Morgan Kaufmann, Los Altos, Los Altos, CA, 1987.

\bibitem{fagi-ullm-vard-83}
R.~Fagin, J.~D. Ullman, and M.~Y. Vardi.
\newblock On the semantics of updates in databases.
\newblock In {\em Proceedings of the Second ACM SIGACT SIGMOD Symposium on
  Principles of Database Systems (PODS'83)}, pages 352--365, 1983.

\bibitem{gare-john-79}
M.~R. Garey and D.~S. Johnson.
\newblock {\em Computers and Intractability: {A} Guide to the Theory of
  {NP}-Completeness}.
\newblock W.H. Freeman and Company, San Francisco, Ca, 1979.

\bibitem{gelf-lifs-88}
M.~Gelfond and V.~Lifschitz.
\newblock The stable model semantics for logic programming.
\newblock In {\em Proceedings of the Fifth Logic Programming Symposium}, pages
  1070--1080. The {MIT} Press, 1988.

\bibitem{gelf-przy-przy-89}
M.~Gelfond, H.~Przymusinska, and T.~Przymusinsky.
\newblock On the relationship between circumscription and negation as failure.
\newblock {\em Artificial Intelligence}, 38:49--73, 1989.

\bibitem{gins-86}
M.~L. Ginsberg.
\newblock Conterfactuals.
\newblock {\em Artificial Intelligence}, 30:35--79, 1986.

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

\bibitem{gott-92-b}
G.~Gottlob.
\newblock Complexity results for nonmonotonic logics.
\newblock {\em Journal of Logic and Computation}, 2:397--425, 1992.

\bibitem{gott-95}
G.~Gottlob.
\newblock Translating default logic into standard autoepistemic logic.
\newblock {\em Journal of the {ACM}}, 42:711--740, 1995.

\bibitem{imie-87}
T.~Imielinski.
\newblock Results on translating defaults to circumscription.
\newblock {\em Artificial Intelligence}, 32:131--146, 1987.

\bibitem{janh-98}
T.~Janhunen.
\newblock On the intertranslatability of autoepistemic, default and priority
  logics, and parallel circumscription.
\newblock In {\em 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.

\bibitem{john-90}
D.~S. Johnson.
\newblock A catalog of complexity classes.
\newblock In J.~van Leeuwen, editor, {\em Handbook of Theoretical Computer
  Science}, volume~A, chapter~2, pages 67--161. Elsevier Science Publishers
  (North-Holland), Amsterdam, 1990.

\bibitem{karp-lipt-80}
R.~M. Karp and R.~J. Lipton.
\newblock Some connections between non-uniform and uniform complexity classes.
\newblock In {\em Proceedings of the Twelfth ACM Symposium on Theory of
  Computing (STOC'80)}, pages 302--309, 1980.

\bibitem{kaut-kear-selm-95}
H.~A. Kautz, M.~J. Kearns, and B.~Selman.
\newblock Horn approximations of empirical data.
\newblock {\em Artificial Intelligence}, 74:129--145, 1995.

\bibitem{kaut-selm-91-a}
H.~A. Kautz and B.~Selman.
\newblock Hard problems for simple default logics.
\newblock {\em Artificial Intelligence}, 49:243--279, 1991.

\bibitem{kaut-selm-92-a}
H.~A. Kautz and B.~Selman.
\newblock Forming concepts for fast inference.
\newblock In {\em Proceedings of the Tenth National Conference on Artificial
  Intelligence (AAAI'92)}, pages 786--793, 1992.

\bibitem{khar-roth-96}
R.~Khardon and D.~Roth.
\newblock Reasoning with models.
\newblock {\em Artificial Intelligence}, 87:187--213, 1996.

\bibitem{khar-roth-97}
R.~Khardon and D.~Roth.
\newblock Defaults and relevance in model-based reasoning.
\newblock {\em Artificial Intelligence}, 97:169--193, 1997.

\bibitem{kobl-wata-98}
J.~K\"obler and O.~Watanabe.
\newblock New collapse consequences of {NP} having small circuits.
\newblock {\em {SIAM} Journal on Computing}, 28(1):311--324, 1998.

\bibitem{kola-papa-90}
P.~G. Kolaitis and C.~H. Papadimitriou.
\newblock Some computational aspects of circumscription.
\newblock {\em Journal of the {ACM}}, 37(1):1--14, 1990.

\bibitem{libe-95}
P.~Liberatore.
\newblock Compact representation of revision of {H}orn clauses.
\newblock In Xin Yao, editor, {\em Proceedings of the Eighth Australian Joint
  Artificial Intelligence Conference (AI'95)}, pages 347--354. World
  Scientific, 1995.

\bibitem{libe-98-b}
P.~Liberatore.
\newblock {\em Compilation of intractable problems and its application to
  {A}rtificial {I}ntelligence}.
\newblock PhD thesis, Dipartimento di Informatica e Sistemistica,
  Universit{\`a} di Roma ``La Sapienza'', 1998.
\newblock URL = {\tt ftp://ftp.dis.uniroma1.it/pub/AI/papers/libe-98-c.ps.gz}.

\bibitem{libe-scha-96}
P.~Liberatore and M.~Schaerf.
\newblock The complexity of model checking for belief revision and update.
\newblock In {\em Proceedings of the Thirteenth National Conference on
  Artificial Intelligence (AAAI'96)}, pages 556--561, 1996.

\bibitem{libe-scha-98}
P.~Liberatore and M.~Schaerf.
\newblock The complexity of model checking for propositional default logics.
\newblock In {\em Proceedings of the Thirteenth European Conference on
  Artificial Intelligence (ECAI'98)}, pages 18--22, 1998.

\bibitem{libe-scha-00-b}
P.~Liberatore and M.~Schaerf.
\newblock The compactness of belief revision and update operators.
\newblock Technical report, Dipartimento di Informatica e Sistemistica,
  Universit{\`a} di Roma ``La Sapienza'', 2000.

\bibitem{mare-trus-91-a}
W.~Marek and M.~Truszczy\'nski.
\newblock Autoepistemic logic.
\newblock {\em Journal of the {ACM}}, 38(3):588--619, 1991.

\bibitem{mcca-80}
J.~McCarthy.
\newblock Circumscription - {A} form of non-monotonic reasoning.
\newblock {\em Artificial Intelligence}, 13:27--39, 1980.

\bibitem{mink-82}
J.~Minker.
\newblock On indefinite databases and the closed world assumption.
\newblock In {\em Proceedings of the Sixth International Conference on
  Automated Deduction (CADE'82)}, pages 292--308, 1982.

\bibitem{mose-tenn-96}
Y.~Moses and M.~Tennenholtz.
\newblock Off-line reasoning for on-line efficiency: knowledge bases.
\newblock {\em Artificial Intelligence}, 83:229--239, 1996.

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

\bibitem{reit-80}
R.~Reiter.
\newblock A logic for default reasoning.
\newblock {\em Artificial Intelligence}, 13:81--132, 1980.

\bibitem{schl-87}
J.~S. Schlipf.
\newblock Decidability and definability with circumscription.
\newblock {\em Annals of Pure and Applied Logic}, 35:173--191, 1987.

\bibitem{schl-95-b}
J.~S. Schlipf.
\newblock A survey of complexity and undecidability results for logic
  programming.
\newblock {\em Annals of Mathematics and Artificial Intelligence}, 15:257--288,
  1995.

\bibitem{selm-kaut-96}
B.~Selman and H.~A. Kautz.
\newblock Knowledge compilation and theory approximation.
\newblock {\em Journal of the {ACM}}, 43:193--224, 1996.

\bibitem{stoc-76}
L.~J. Stockmeyer.
\newblock The polynomial-time hierarchy.
\newblock {\em Theoretical Computer Science}, 3:1--22, 1976.

\bibitem{wins-89}
M.~Winslett.
\newblock Sometimes updates are circumscription.
\newblock In {\em Proceedings of the Eleventh International Joint Conference on
  Artificial Intelligence (IJCAI'89)}, pages 859--863, 1989.

\bibitem{wins-90}
M.~Winslett.
\newblock {\em Updating Logical Databases}.
\newblock Cambridge University Press, 1990.

\bibitem{yap-83}
C.~K. Yap.
\newblock Some consequences of non-uniform conditions on uniform classes.
\newblock {\em Theoretical Computer Science}, 26:287--300, 1983.

\end{thebibliography}
