Next: About this document ...
Up: The Complexity of Reasoning
Previous: Acknowledgments.

 ABM99

C. Areces, P. Blackburn, and M. Marx.
A roadmap on complexity for hybrid logics.
In Proceedings of the Annual Conference of the European
Association for Computer Science Logic (CSL99), LNCS 1683, pages
307321. SpringerVerlag, 1999.
 BBH96

F. Baader, M. Buchheit, and B. Hollunder.
Cardinality restrictions on concepts.
Artificial Intelligence, 88(12):195213, 1996.
 Ber66

R. Berger.
The undecidability of the dominoe problem.
Memoirs of the American Mathematical Society, 66, 1966.
 BGG97

Egon Börger, Erich Grädel, and Yuri Gurevich.
The Classical Decision Problem.
Perspectives in Mathematical Logic. SpringerVerlag, Berlin, 1997.
 Bor96

A. Borgida.
On the relative expressiveness of description logics and first order
logics.
Artificial Intelligence, 82:353367, 1996.
 BPS94

Alex Borgida and Peter F. PatelSchneider.
A semantic and complete algorithm for subsumption in the classic
description logic.
Journal of Artificial Intelligence Research, 1:277308, 1994.
 BS96

P. Blackburn and J. Seligman.
Hybrid languages.
Journal of Logic, Language and Information, 3(4):251272,
1996.
 BS99

F. Baader and U. Sattler.
Expressive number restrictions in description logics.
Journal of Logic and Computation, 9(3):319350, 1999.
 CDGL98a

Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini.
On the decidability of query containment under constraints.
In Proceedings of the Seventeenth ACM SIGACT SIGMOD SIGART
Symposium on Principles of Database Systems (PODS98), 1998.
 CDGL^{+}98b

Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Daniele Nardi, and
Riccardo Rosati.
Description logic framework for information integration.
In Proc. of the 6th Int. Conf. on the Principles of Knowledge
Representation and Reasoning (KR'98), pages 213, 1998.
 CDL^{+}98

D. Calvanese, G. De Giacomo, M. Lenzerini, D. Nardi, and R. Rosati.
Source integration in data warehousing.
In Proceedings of the Ninth International Workshop on Database
and Expert Systems Applications (DEXA98), pages 192197. IEEE Computer
Society Press, 1998.
 De 95

G. De Giacomo.
Decidability of ClassBased Knowledge Representation
Formalisms.
PhD thesis, Dip. di Inf. e Sist., Univ. di Roma ``La Sapienza'',
1995.
 DL96

G. De Giacomo and M. Lenzerini.
TBox and ABox reasoning in expressive description logics.
In L. C. Aiello, J. Doyle, and S. C. Shapiro, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the
Fifth International Conference (KR'96), pages 316327. Morgan Kaufmann
Publishers, San Francisco, California, November 1996.
 DLNS96

Francesco M. Donini, Maurizio Lenzerini, Daniele Nardi, and Andrea Schaerf.
Reasoning in description logics.
In Gerhard Brewka, editor, Foundation of Knowledge
Representation, pages 191236. CSLIPublications, 1996.
 Fin72

K. Fine.
In so many possible worlds.
Notre Dame Journal of Formal Logic, 13:516520, 1972.
 GG93

George Gargov and Valentin Goranko.
Modal logic with names.
J. of Philosophical Logic, 22:607636, 1993.
 GOR97

Erich Grädel, Martin Otto, and Eric Rosen.
Twovariable logic with counting is decidable.
In Proceedings, Twelth Annual IEEE Symposium on Logic in
Computer Science, pages 306317, Warsaw, Poland, 29 June2 July 1997. IEEE
Computer Society Press.
 HM92

J. Y. Halpern and Y. Moses.
A guide to completeness and complexity for model logics of knowledge
and belief.
Artificial Intelligence, 54(3):319379, April 1992.
 HST99

I. Horrocks, U. Sattler, and S. Tobies.
Practical reasoning for expressive
description logics.
In Proceedings of the 6th International Conference on Logic for
Programming and Automated Reasoning (LPAR'99), pages 161180, 1999.
 Pra79

V. R. Pratt.
Models of program logics.
In Proceedings of the Twentieth IEEE Symposium on Foundations
of Computer Science, pages 115122. IEEE, 1979.
 PST97

Leszek Pacholski, Wiesaw Szwast, and Lidia Tendera.
Complexity of twovariable logic with counting.
In Proceedings, Twelth Annual IEEE Symposium on Logic in
Computer Science, pages 318327, Warsaw, Poland, 29 June2 July 1997. IEEE
Computer Society Press.
 Spa93

Edith Spaan.
Complexity of Modal Logics.
PhD thesis, University of Amsterdam, 1993.
 SSS91

M. SchmidtSchauß and G. Smolka.
Attributive concept descriptions with complements.
Artificial Intelligence, 48:126, 1991.
 Tob99

S. Tobies.
A NExpTimecomplete description logic strictly contained in
C^{2}.
In J. Flum and M. RodríguezArtalejo, editors, Proceedings
of the Annual Conference of the European Association for Computer Science
Logic (CSL99), LNCS 1683, pages 292306. SpringerVerlag, 1999.
 Tob00

Stephan Tobies.
PSPACE reasoning for graded modal logics.
Journal of Logic and Computation, 10(1):122, 2000.
To appear.
 Var97

Moshe Y. Vardi.
Why is modal logic so robustly decidable?
In Descriptive Complexity and Finite Models: Proceedings of a
DIMACS Workshop, January 1417, 1996, number 31 in DIMACS Series in Discrete
Mathematics and Theoretical Computer Science, pages 149184. American Math.
Society, 1997.
 Wan63

H. Wang.
Dominoes and the AEA case of the Decision Problem.
Bell Syst. Tech. J., 40:141, 1963.
 WS92

W. A. Woods and J. G. Schmolze.
The
family.
Computers and Mathematics with Applications  Special Issue on
Artificial Intelligence, 23(25):133177, 1992.
Stephan Tobies
May 02 2000