Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-26T17:53:53.890Z Has data issue: false hasContentIssue false
  • English
  • Français

Decidable fragments of first-order modal logics

Published online by Cambridge University Press:  12 March 2014

Frank Wolter  and
Michael Zakharyaschev
Frank Wolter
Affiliation:
Institut für Informatik, Universität Leipzig, Augustus-Platz 10-11, 04109 Leipzig, Germany, E-mail: [email protected]
Michael Zakharyaschev
Affiliation:
Department of Computer Science, King's College London, Strand, London WC2R 2LS, UK, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The paper considers the set of first-order polymodal formulas the modal operators in which can be applied to subformulas of at most one free variable. Using a mosaic technique, we prove a general satisfiability criterion for formulas in , which reduces the modal satisfiability to the classical one. The criterion is then used to single out a number of new, in a sense optimal, decidable fragments of various modal predicate logics.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 66 , Issue 3 , September 2001 , pp. 1415 - 1438
Copyright
Copyright © Association for Symbolic Logic 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Andréka, H., van Benthem, J., and Németi, I., Modal languages and bounded fragments of predicate logic, Journal of Philosophical Logic, vol. 27 (1998), pp. 217–274.CrossRefGoogle Scholar
[2]Artemov, S. and Dzhaparidze, G., Finite Kripke models and predicate logics of provability, this Journal, vol. 55 (1990), pp. 1090–1098.Google Scholar
[3]Baader, F. and Laux, A., Terminological logics with modal operators, Proceedings of the 14th International Joint Conference on Artificial Intelligence (Montreal, Canada), Morgan Kaufman, 1995, pp. 808–814.Google Scholar
[4]Baader, F. and Ohlbach, H.J., A multi-dimensional terminological knowledge representation language, Journal of Applied Non-Classical Logic, vol. 5 (1995), pp. 153–197.CrossRefGoogle Scholar
[5]Behmann, H., Beiträge zur Algebra der Logik, inbesondere zum Entscheidungsproblem, Math. Ann., vol. 86 (1922), pp. 163–229.CrossRefGoogle Scholar
[6]Börger, E., Grädel, E., and Gurevich, Yu., The classical decision problem, Perspectives in Mathematical Logic, Springer, 1997.CrossRefGoogle Scholar
[7]Brachman, R. J. and Schmölze, J.G., An overview of the KL-ONE knowledge representation system, Cognitive Science, vol. 9 (1985), pp. 171–216.Google Scholar
[8]Calvanese, D., De Giacomo, G., Nardi, D., and Lenzerini, M., Reasoning in expressive description logics, Handbook of automated reasoning (Robinson, A. and Voronkov, A., editors), Elsevier Science Publishers B.V., 2000, In print.Google Scholar
[9]Chagrov, A.V. and Zakharyaschev, M.V., Modal logic, Oxford Logic Guides 35, Clarendon Press, Oxford, 1997.CrossRefGoogle Scholar
[10]Fischer-Servi, G., The finite model property for MIPQ and some consequences, Notre Dame Journal of Formal Logic, vol. 19 (1978), pp. 687–692.CrossRefGoogle Scholar
[11]Gabbay, D. and Shehtman, V., Undecidubility of modal and intermediate first-order logics with two individual variables, this Journal, vol. 58 (1993), pp. 800–823.Google Scholar
[12]Gabbay, D. and Shehtman, V., Products of modal logics. Part I, Journal of the IGPL, vol. 6 (1998), pp. 73–146.CrossRefGoogle Scholar
[13]Gabbay, D. and Shehtman, V., Products of modal logics. Part II, Journal of the IGPL, vol. 8 (2000).CrossRefGoogle Scholar
[14]Ganzinger, H., Meyer, C., and Veanes, M., The two-variable guarded fragment with transitive relations, Proceedings of the 14th ieee symposium, 1999, pp. 24–34.Google Scholar
[15]de Giacomo, G., Decidability of class-based knowledge representation formalisms, Ph.D. thesis, Univ. di Roma, 1995.Google Scholar
[16]de Giacomo, G. and Lenzerini, M., TBox and ABox reasoning in expressive description logics, Proceedings of the fifth conference on principles of knowledge representation and reasoning (Montreal, Canada), Morgan Kaufman, 1996.Google Scholar
[17]Gräber, A., Bürckert, H., and Laux, A., Terminological reasoning with knowledge and belief, Knowledge and belief in philosophy and artificial intelligence (Laux, A. and Wansing, H., editors), Akademie Verlag, 1995, pp. 29–61.Google Scholar
[18]Grädel, E., Decision procedures for guarded logics, Automated Deduction—CADE-16, Proceedings ofthe 16th International Conference on Automated Deduction, Lecture Notes in Artificial Intelligence, vol. 1632, Springer, 1999.Google Scholar
[19]Grädel, E., On the restraining power of guards, this Journal, vol. 64 (1999), pp. 1719–1742.Google Scholar
[20]Harel, D., Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness, Journal of the ACM, vol. 33 (1986), pp. 224–248.CrossRefGoogle Scholar
[21]Hirsch, R., Hodkinson, I., and Kurucz, A., Onmodal logics between K × K × K and S5 × S5 × S5, Manuscript; available at http://www.doc.ic.ac.uk/~kuag/k3undec.ps, 2000.Google Scholar
[22]Hodkinson, I., Loosely guarded fragment has the finite model property, Manuscript; available at http://www.doc.ic.ac.uk/~imh, 2000.Google Scholar
[23]Hodkinson, I., Wolter, F., and Zakharyaschev, M., Decidable fragments of first-order temporal logics, Annals of Pure and Applied Logic, (2000), In print.Google Scholar
[24]Hughes, G.E. and Cresswell, M.J., A new introduction to modal logic, Methuen, London, 1996.CrossRefGoogle Scholar
[25]Kripke, S., The undecidability of monadic modal quantificational theory, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 8 (1962), pp. 113–116.CrossRefGoogle Scholar
[26]Laux, A., Beliefs in multi-agent worlds: a terminological approach, Proceedings of the 11th european conference on artificial intelligence (Amsterdam), 1994, pp. 299–303.Google Scholar
[27]Löwenheim, L., Über Möglichkeiten im Relativkalkül, Mathematische Annalen, vol. 76 (1915), pp. 447–470.CrossRefGoogle Scholar
[28]Lutz, C., Sturm, H., Wolter, F., and Zakharyaschev, M., A tableau for K based on ALE with constant domains, Manuscript; available at http://www.informatik.uni-leipzig.de/~wolter, 2000.Google Scholar
[29]Marx, M., Packed fragment and relativized semantics, Manuscript, ILLC, University of Amsterdam, 1998.Google Scholar
[30]Marx, M., Complexity of products of modal logics, Journal of Logic and Computation, vol. 9 (1999), pp. 197–214.CrossRefGoogle Scholar
[31]Mortimer, M., On languages with two variables, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 21 (1975), pp. 135–140.CrossRefGoogle Scholar
[32]Purdy, W.C., Fluted formulas and the limits of decidability, this Journal, vol. 61 (1996), pp. 608–620.Google Scholar
[33]Schild, K., A correspondence theory for terminological logics: preliminary report, Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI-91) (Sydney), 1991, pp. 466–471.Google Scholar
[34]Schild, K., Combining terminological logics with tense logic, Proceedings of the 6th Portuguese conference on artificial intelligence (Porto), 1993, pp. 105–120.Google Scholar
[35]Schmidt-Schauß, M. and Smolka, G., Attributive concept descriptions with complements, Artificial Intelligence, vol. 48 (1991), pp. 1–26.CrossRefGoogle Scholar
[36]Scott, D., A decision method for validity of sentences in two variables, this Journal, vol. 27 (1962), p. 477.Google Scholar
[37]Segerberg, K., Two-dimensional modal logic, Journal of Philosophical Logic, vol. 2 (1973), pp. 77–96.CrossRefGoogle Scholar
[38]Shehtman, V., On some two-dimensional modal logics, Proceedings of the 8th International Congress on Logic, Methodology, and Philosophy of Science (Moscow), vol. 1, 1987, pp. 326–330.Google Scholar
[39]Spaan, E., Complexity of modal logics, Ph.D. thesis, Department of Mathematics and Computer Science, University of Amsterdam, 1993.Google Scholar
[40]Sturm, H. and Wolter, F., A tableau calculus for temporal description logic: expanding domain case, Journal of Logic and Computation, to appear.Google Scholar
[41]Sturm, H., Wolter, F., and Zakharyaschev, M., Monodie epistemic predicate logic, Proceedings of JELIA, Lecture Notes in Artificial Intelligence, Springer, 2000.Google Scholar
[42]Surányi, J., Zur Reduktion des Entscheidungsproblems des logischen Funktionskalküls, Mathematikai és Fizikai Lepok, vol. 50 (1943), pp. 51–74.Google Scholar
[43]van Benthem, J., Exploring logical dynamics, CSLI Publications, Stanford, 1996.Google Scholar
[44]van Benthem, J., Dynamic bits and pieces, Technical Report LP–97–01, ILLC, University of Amsterdam, 1997.Google Scholar
[45]Wajsberg, M., Ein erweiter Klassenkalkül, Monatshefte für Mathematik und Physik, vol. 40 (1933), pp. 113–126.CrossRefGoogle Scholar
[46]Wolter, F. and Zakharyaschev, M., Satisfiability problem in description logics with modal operators, Proceedings of the sixth Conference on Principles of Knowledge Representation and Reasoning (Montreal, Canada), Morgan Kaufman, 1998, pp. 512–523.Google Scholar
[47]Wolter, F. and Zakharyaschev, M., Modal description logics: modalizing roles, Fundamenta Informaticae, vol. 39 (1999), pp. 411–438.CrossRefGoogle Scholar
[48]Wolter, F. and Zakharyaschev, M., Axiomatizing the monodic fragment offirst-order temporal logic, Manuscript; available at http://www.informatik.uni-leipzig.de/~wolter, 2000.Google Scholar
[49]Wolter, F. and Zakharyaschev, M., Dynamic description logic, Advances in modal logic, volume 2 (Zakharyaschev, M., Segerberg, K., de Rijke, M., and Wansing, H., editors), CSLI Publications, 2000.Google Scholar
[50]Wolter, F. and Zakharyaschev, M., Temporalizing description logics, Frontiers of combining systems 2 (Baldock, England) (Gabbay, D. and de Rijke, M., editors), Research Studies Press Ltd, 2000, pp. 379–401.Google Scholar
[51]Zamov, N., Maslov's inverse method and decidable classes, Annals of Pure and Applied Logic, vol. 42 (1989), pp. 165–194.CrossRefGoogle Scholar