Skip to main content
SpringerLink
Log in

On Modal Logics Characterized by Models with Relative Accessibility Relations: Part I

  • Published:
Studia Logica Aims and scope Submit manuscript

Abstract

This work is divided in two papers (Part I and Part II). In Part I, we study a class of polymodal logics (herein called the class of "Rare-logics") for which the set of terms indexing the modal operators are hierarchized in two levels: the set of Boolean terms and the set of terms built upon the set of Boolean terms. By investigating different algebraic properties satisfied by the models of the Rare-logics, reductions for decidability are established by faithfully translating the Rare-logics into more standard modal logics. The main idea of the translation consists in eliminating the Boolean terms by taking advantage of the components construction and in using various properties of the classes of semilattices involved in the semantics. The novelty of our approach allows us to prove new decidability results (presented in Part II), in particular for information logics derived from rough set theory and we open new perspectives to define proof systems for such logics (presented also in Part II).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Ph. Balbiani, ‘A modal logic for data analysis’, in W. Penczek and A. Szalas (eds.), MFCS'96, Kraków, p. 167–179, LNCS 1113, Springer-Verlag, 1996.

  2. Ph. Balbiani, ‘Modal logics with relative accessibility relations’, in D. Gabbay and H. J. Ohlbach (eds.), FAPR'96, Bonn, p. 29–41, LNAI, Springer-Verlag, 1996.

  3. Ph. Balbiani, ‘Axiomatization of logics based on Kripke models with relative accessibility relations’, in [Oe97], p. 553–578, 1997.

    Google Scholar 

  4. Ph. Balbiani, and E. OrŁowska, ‘A hierarchy of modal logics with relative accessibility relations’, Journal of Applied Non-Classical Logics, special issue in the Memory of George Gargov, 9: 303–328, 1999.

    Google Scholar 

  5. S. Demri, ‘A logic with relative knowledge operators’, Journal of Logic, Language and Information 8(2): 167–185, 1999.

    Google Scholar 

  6. S. Demri and D. Gabbay, ‘On modal logics characterized by models with relative accessibility relations: Part II’, this journal (to appear).

  7. M. d'Agostino and D. Gabbay, ‘A generalization of analytic deduction via labelled deductive systems. Part I: Basic substructural logics’, Journal of Automated Reasoning 13: 243–281, 1994.

    Google Scholar 

  8. S. Demri and R. GorÉ, ‘Display calculi for logics with relative accessibility relations’, Technical Report TR-ARP–04–98, Automated Reasoning Project, Australian National University, May 1998.

  9. S. Demri and E. OrŁowska, ‘Logical analysis of indiscernibility’, in [Oe97], p. 347–380, 1997.

    Google Scholar 

  10. B. Davey and H. Priestley, Introduction to Lattices and Order, Cambridge Mathematical Textbooks, Cambridge University Press, 1990.

  11. I. DÜntsch, ‘Rough sets and algebras of relations’, in [Oe97], p. 95–108, 1997.

    Google Scholar 

  12. L. FariÑas Del Cerro and E. OrŁowska, ‘DAL — A logic for data analysis’, Theoretical Computer Science 36: 251–264, 1985.

    Google Scholar 

  13. G. Gargov, ‘Two completeness theorems in the logic for data analysis’, Technical Report 581, ICS, Polish Academy of Sciences, Warsaw, 1986.

    Google Scholar 

  14. G. Gargov and S. Passy, ‘A note on boolean modal logic’, in P. Petkov (ed.), Summer School and Conference on Mathematical Logic '88, p. 299–309, Plenum Press, 1990.

  15. V. Goranko and S. Passy, ‘Using the universal modality: gains and questions’, Journal of Logic and Computation 2(1): 5–30, 1992.

    Google Scholar 

  16. R. Goldblatt and S. Thomason, ‘Axiomatic classes in propositional modal logic’, in J. Crossley (ed.), Algebra and Logic, p. 163–173, Springer-Verlag, Lecture Notes in Mathematics 450, 1975.

  17. V. Goranko and D. Vakarelov, ‘Hyperboolean algebras and hyperboolean modal logic’, Technical Report 1/98, January 1998.

  18. D. Harel, ‘Dynamic logic’, in D. Gabbay and F. Guenthner (eds.), Handbook of Philosophical Logic, Volume II, p. 497–604, Reidel, Dordrecht, 1984.

    Google Scholar 

  19. A. Herzig and H. J. Ohlbach, ‘Parameter structures for parametrized modal operators’, in IJCAI '91, 1991.

  20. J. JÄrvinen, ‘Representation of information systems and dependences spaces, and some basic algorithms’, Licentiate's thesis, 1997.

  21. B. Konikowska, ‘A formal language for reasoning about indiscernibility’, Bulletin of the Polish Academy of Sciences 35: 239–249, 1987.

    Google Scholar 

  22. B. Konikowska, ‘A logic for reasoning about relative similarity’, Studia Logica 58(1): 185–226, 1997.

    Google Scholar 

  23. B. Konikowska, ‘A logic for reasoning about similarity’, in [Oe97], p. 462–491, 1997.

    Google Scholar 

  24. E. Lemmon, Beginning Logic, Chapman and Hall, 1965.

  25. M. Novotny, ‘Applications of dependence spaces’, in [Oe97], p. 247–289, 1997.

    Google Scholar 

  26. E. OrŁowska (ed.), Incomplete Information: Rough Set Analysis, Studies in Fuzziness and Soft Computing, Physica-Verlag, Heidelberg, 1997.

    Google Scholar 

  27. E. OrŁowska and Z. Pawlak, ‘Expressive power of knowledge representation systems’, Int. Journal Man-Machines Studies 20: 485–500, 1984.

    Google Scholar 

  28. E. OrŁowska, ‘Logic of indiscernibility relations’, in A. Skowron (ed.), 5th Symposium on Computation Theory, Zaborów, Poland, p. 177–186, LNCS 208, Springer-Verlag, 1984.

  29. E. OrŁowska, ‘Logic of nondeterministic information’, Studia Logica 44: 93–102, 1985.

    Google Scholar 

  30. E. OrŁowska, ‘Kripke models with relative accessibility and their applications to inferences from incomplete information’, in G. Mirkowska and H. Rasiowa (eds.), Mathematical Problems in Computation Theory, p. 329–339, Banach Center Publications, Volume 21 PWN — Polish Scientific Publishers, Warsaw, 1988.

    Google Scholar 

  31. E. OrŁowska, ‘Logical aspects of learning concepts’, Journal of Approximate Reasoning 2: 349–364, 1988.

    Google Scholar 

  32. E. OrŁowska, ‘Logic for reasoning about knowledge’, Zeitschr. f. Math. Logik und Grundlagen d. Math. 35: 559–568, 1989.

    Google Scholar 

  33. E. OrŁowska, ‘Kripke semantics for knowledge representation logics’, Studia Logica 49(2): 255–272, 1990.

    Google Scholar 

  34. E. OrŁowska, ‘Reasoning with incomplete information: rough set based information logics’, in V. Alagar, S. Bergler, and F. Q. Dong (eds.), Incompleteness and Uncertainty in Information Systems Workshop, p. 16–33, Springer-Verlag, October 1993.

  35. E. OrŁowska, ‘Information algebras’, in AMAST'95, Montreal, p. 50–65, LNCS 639, Springer-Verlag, 1995.

  36. E. OrŁowska, ‘Introduction: What you always wanted to know about rough sets’, in [Oe97], p. 1–20, 1997.

    Google Scholar 

  37. P. Pagliani, ‘Rough set theory and logic-algebraic structures’, in [Oe97], p. 109–192, 1997.

    Google Scholar 

  38. Ch. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Compoany, 1994.

  39. Z. Pawlak, ‘Information systems theoretical foundations’, Information Systems 6(3): 205–218, 1981.

    Google Scholar 

  40. V. Pratt, ‘Applications of modal logic to programming’, Studia Logica 39: 257–274, 1980.

    Google Scholar 

  41. C. Rauszer, ‘An equivalence between indiscernibility relations in information systems and a fragment of intuitionistic logic’, in A. Skowron (ed.), 5th Symposium on Computation Theory, Zaborów, Poland, pages 298–317. LNCS 208, Springer-Verlag, 1984.

  42. D. Vakarelov, ‘Logical analysis of positive and negative similarity relations in property systems’, in M. de Glas and D. Gabbay (eds.), First World Conference on the Fundamentals of Artificial Intelligence, 1991.

  43. D. Vakarelov, ‘A modal logic for similarity relations in Pawlak knowledge representation systems’, Fundamenta Informaticae 15: 61–79, 1991.

    Google Scholar 

  44. D. Vakarelov, ‘Modal logics for knowledge representation systems’, Theoretical Computer Science 90: 433–456, 1991.

    Google Scholar 

  45. D. Vakarelov, ‘A modal logic for cyclic repeating’, Information and Computation 101: 103–122, 1992.

    Google Scholar 

  46. D. Vakarelov, ‘Information systems, similarity and modal logics’, in [Oe97], p. 492–550, 1997.

    Google Scholar 

  47. Y. Venema, Many-dimensional modal logic, PhD thesis, FWI, Amsterdam University, September 1991.

Download references

Author information

Authors and Affiliations

  1. Laboratoire LEIBNIZ, 46 av. Félix Viallet, 38000, Grenoble, France

    Stéphane Demri

  2. King's College STRAND, London, WC2R 2LS, United Kingdom

    Dov Gabbay

Authors
  1. Stéphane Demri
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dov Gabbay
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Demri, S., Gabbay, D. On Modal Logics Characterized by Models with Relative Accessibility Relations: Part I. Studia Logica 65, 323–353 (2000). https://doi.org/10.1023/A:1005235713913

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1005235713913

Search

Navigation