On semantically labelled syntax trees and the non-existence of certain Sahlqvist formulae

被引：1
作者：
Iliev, Petar [1 ,2 ]
机构：
[1] Bulgarian Acad Sci, Inst Math & Informat, Sofia 1000, Bulgaria
[2] Bulgarian Acad Sci, Inst Philosophy & Sociol, Sofia 1000, Bulgaria
来源：
LOGIC JOURNAL OF THE IGPL | 2023年 / 31卷 / 03期
关键词：
Modal logic; model theory of modal logic; correspondence theory; Sahlqvist formulae; semantic labelling of syntax trees; LOWER BOUNDS; SUCCINCTNESS; GAMES;
D O I：
10.1093/jigpal/jzac044
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We elaborate on semantically labelled syntax trees that provide a method of proving the non-existence of modal formulae satisfying certain syntactic properties and defining a given class of frames and use them to show that there are classes of Kripke frames that are definable by both non-Sahlqvist and Sahlqvist formulae, but the latter requires more propositional variables.
引用
收藏
页码：483 / 509
页数：27
相关论文
共 21 条
  • [1] Adler M., 2003, ACM Transactions on Computational Logic, V4, P296, DOI 10.1145/772062.772064
  • [2] [Anonymous], 2011, P IJCAI
  • [3] [Anonymous], 2010, P ADV MODAL LOGIC
  • [4] [Anonymous], 1997, Oxford Logic Guides
  • [5] Balbiani P., 2018, P ADV MODAL LOGIC, P83
  • [6] Frame-validity games and lower bounds on the complexity of modal axioms
    Balbiani, Philippe
    Fernandez-Duque, David
    Herzig, Andreas
    Iliev, Petar
    [J]. LOGIC JOURNAL OF THE IGPL, 2022, 30 (01) : 155 - 185
  • [7] Blackburn P., 2010, Cambridge Tracts in Theoretical Computer Science, V53
  • [8] Algebraic modal correspondence: Sahlqvist and beyond
    Conradie, Willem
    Palmigiano, Alessandra
    Sourabh, Sumit
    [J]. JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN PROGRAMMING, 2017, 91 : 60 - 84
  • [9] Fernández-Duque D, 2018, J APPL LOG-IFCOLOG, V5, P827
  • [10] On the succinctness of some modal logics
    French, Tim
    van der Hoek, Wiebe
    Iliev, Petar
    Kooi, Barteld
    [J]. ARTIFICIAL INTELLIGENCE, 2013, 197 : 56 - 85
123