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 条

[11] Elementary canonical formulae: extending Sahlqvist's theorem
Goranko, Valentin
Vakarelov, Dimiter
[J]. ANNALS OF PURE AND APPLIED LOGIC, 2006, 141 (1-2) : 180 - 217
[12] THE SUCCINCTNESS OF FIRST-ORDER LOGIC ON LINEAR ORDERS
Grohe, Martin
Schweikardt, Nicole
[J]. LOGICAL METHODS IN COMPUTER SCIENCE, 2005, 1 (01)
[13] Hella Lauri, 2016, Advances in Modal Logic, V11, P401
[14] Formula size games for modal logic and μ-calculus
Hella, Lauri T.
Vilander, Miikka S.
[J]. JOURNAL OF LOGIC AND COMPUTATION, 2019, 29 (08) : 1311 - 1344
[15] Karchmer M, 1995, FEASIBLE MATH, V13
[16] APPLICATIONS OF MATRIX-METHODS TO THE THEORY OF LOWER BOUNDS IN COMPUTATIONAL-COMPLEXITY
RAZBOROV, AA
[J]. COMBINATORICA, 1990, 10 (01) : 81 - 93
[17] Sahlqvist H., 1975, P 3 SCAND LOG S, P110, DOI DOI 10.1016/S0049-237X(08)70728-6
[18] A NEW PROOF OF SAHLQVIST THEOREM ON MODAL DEFINABILITY AND COMPLETENESS
SAMBIN, G
VACCARO, V
[J]. JOURNAL OF SYMBOLIC LOGIC, 1989, 54 (03) : 992 - 999
[19] Vakarelov D., 2003, Proceedings of Advances in Modal Logic, V4, P499
[20] van der Hoek W, 2014, AAMAS'14: PROCEEDINGS OF THE 2014 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS, P341

← 1 2 3 →