Frame-validity games and lower bounds on the complexity of modal axioms

被引：2

作者：

Balbiani, Philippe ^{[1
]}

Fernandez-Duque, David ^{[2
]}

Herzig, Andreas ^{[1
]}

Iliev, Petar ^{[3
]}

机构：

[1] Toulouse Univ, CNRS, IRIT, F-31062 Toulouse, France

[2] Univ Ghent, Dept Math, B-9000 Ghent, Belgium

[3] Bulgarian Acad Sci, Inst Philosophy & Sociol, Sofia 1000, Bulgaria

来源：

LOGIC JOURNAL OF THE IGPL | 2022年 / 30卷 / 01期

关键词：

Modal logic; correspondence theory; formula-size games; lower bounds on formula-size; SUCCINCTNESS;

D O I：

10.1093/jigpal/jzaa068

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We introduce frame-equivalence games tailored for reasoning about the size, modal depth, number of occurrences of symbols and number of different propositional variables of modal formulae defining a given frame property. Using these games, we prove lower bounds on the above measures for a number of well-known modal axioms; what is more, for some of the axioms, we show that they are optimal among the formulae defining the respective class of frames.

引用

页码：155 / 185

页数：31

共 27 条

[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], 1999, Descriptive Complexity
[5] [Anonymous], 2006, P 5 INT JOINT C AUT, P137, DOI DOI 10.1145/1160633.1160657
[6] Balbiani Philippe, 2007, Fundamenta Informaticae, V81, P29
[7] Balbiani P., 2018, P ADV MODAL LOGIC, P83
[8] Chagrov A.V., 1997, MODAL LOGIC, V35
[9] EBBINGHAUS H. -D., 1995, FINITE MODEL THEORY
[10] Ehrenfeucht A., 1961, FUND MATH, V49, P129, DOI [10.4064/fm-49-2-129-141, DOI 10.4064/FM-49-2-129-141]

← 1 2 3 →