Definability and Canonicity for Boolean Logic with a Binary Relation

• Autorzy: Balbiani P. , Tinchev T.

Identyfikatory

DOI

10.3233/FI-2014-973

• Języki publikacji: EN

Abstrakty

EN

This paper studies the concepts of definability and canonicity in Boolean logic with a binary relation. Firstly, it provides formulas defining first-order or second-order conditions on frames. Secondly, it proves that all formulas corresponding to compatible first-order conditions on frames are canonical.

Słowa kluczowe

EN

Boolean algebra; modal logic; definability; canonicity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 129, nr 4
• Strony: 301--327
• Opis fizyczny: Bibliogr. 31 poz.

Twórcy

autor

Balbiani P.

• Institut de recherche en informatique de Toulouse, CNRS — Universit´e de Toulouse 118 route de Narbonne, 31062 Toulouse Cedex 9, France

autor

Tinchev T.

• Department of Mathematical Logic and Applications, Sofia University Blvd James Bouchier 5, 1126 Sofia, Bulgaria

Bibliografia

• [1] Balbiani, P., Kikot, S.: Sahlqvist theorems for precontact logics. In: Advances in Modal Logic. Volume 9. College Publications (2012) 55–70.
• [2] Balbiani, P., Tinchev, T.: Definability over the class of all partitions. Journal of Logic and Computation 16 (2006) 541–557.
• [3] Balbiani, P., Tinchev, T.: Boolean logics with relations. Journal of Logic and Algebraic Programming 79 (2010) 707–721.
• [4] Balbiani, P., Tinchev, T., Vakarelov, D.: Dynamic logics of the region-based theory of discrete spaces. Journal of Applied Non-Classical Logics 17 (2007) 39–61.
• [5] Balbiani, P., Tinchev, T., Vakarelov, D.: Modal logics for region-based theories of space. Fundamenta Informaticæ 81 (2007) 29–82.
• [6] Biacino, L., Gerla, G.: Connection structures: Grzegorczyk’s and Whitehead’s definition of point. Notre Dame Journal of Formal Logic 37 (1996) 431–439.
• [7] Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic. Cambridge University Press (2001).
• [8] Chagrov, A., Chagrova, L.: The truth about algorithmic problems in correspondence theory. In: Advances in Modal Logic. Volume 6. College Publications (2006) 121–138.
• [9] Chagrov, A., Zakharyaschev,M.: Modal Logic. Oxford University Press (1997).
• [10] Clarke, B.: A calculus of individuals based on “connection”. Notre Dame Journal of Formal Logic 22 (1981) 204–219.
• [11] Cohn, A., Hazarika, S.: Qualitative spatial representation and reasoning: an overview. Fundamenta Informaticæ 46 (2001) 1–29.
• [12] Dimov, G., Vakarelov, D.: Contact algebras and region-based theory of space: a proximity approach – I. Fundamenta Informaticæ 74 (2006) 209–249.
• [13] Dimov, G., Vakarelov, D.: Contact algebras and region-based theory of space: proximity approach – II. Fundamenta Informaticæ 74 (2006) 251–282.
• [14] D¨untsch, I., Vakarelov, D.: Region-based theory of discrete spaces: a proximity approach. Annals of Mathematics and Artificial Intelligence 49 (2007) 5–14.
• [15] Düntsch, I., Wang, H., McCloskey, S..: A relational algebraic approach to Region Connection Calculus. Theoretical Computer Science 255 (2001) 63–83.
• [16] Düntsch, I., Winter, M.: A representation theorem for Boolean contact algebras. Theoretical Computer Science 347 (2005) 498–512.
• [17] Galton, A.: The mereotopology of discrete space. In: Spatial Information Theory. Springer (1999) 251–266.
• [18] Galton, A.: Qualitative Spatial Change. Oxford University Press (2000).
• [19] Goldblatt, R., Thomason, S.: Axiomatic classes in propositional modal logic. In: Algebra and Logic. Springer (1975) 163–173.
• [20] Grädel, E., Kolaitis, P., Vardi, M.: On the decision problem for two-variable first-order logic. Bulletin of Symbolic Logic 3 (1997) 53–69.
• [21] Grzegorczyk, A.: Axiomatization of geometry without points. Synthese 12 (1960) 228–235.
• [22] De Laguna, T.: Point, line and surface, as sets of solids. The Journal of Philosophy 19 (1922) 449–461.
• [23] Mortimer, M.: On languages with two variables. Zeitschrift für mathematische Logik und Grundlagen der Mathematik 21 (1975) 135–140.
• [24] Sahlqvist, H.: Completeness and correspondence in the first and second order semantics for modal logic. In: Proceedings of the Third Scandinavian Logic Symposium. North-Holland (1975) 110–143.
• [25] Sambin, G., Vaccaro, V.: A new proof of Sahlqvist theorem on modal definability and completeness. The Journal of Symbolic Logic 54 (1989) 992–999.
• [26] Stell, J.: Boolean connection algebras: a new approach to the region-connection calculus. Artificial Intelligence 122 (2000) 111–136.
• [27] Vakarelov, D.: Region-based theory of space: algebras of regions, representation theory, and logics. In: Mathematical Problems from Applied Logic. Logics for the XXIst Century. II. Springer (2007) 267–348.
• [28] Vakarelov, D., Dimov, G., Düntsch, I., Bennett, B.: A proximity approach to some region-based theory of space. Journal of Applied Non-Classical Logics 12 (2002) 527–559.
• [29] De Vries, H.: Compact Spaces and Compactifications: an Algebraic Approach. Van Gorcum (1962).
• [30] Wechler, W.: Universal Algebra for Computer Scientists. Springer (1992).
• [31] Whitehead, A.: Process and Reality. MacMillan (1929).