The Completeness Problem for Modal Logic

被引：2

作者：

Achilleos, Antonis ^{[1
]}

机构：

[1] Reykjavik Univ, Sch Comp Sci, Reykjavik, Iceland

来源：

LOGICAL FOUNDATIONS OF COMPUTER SCIENCE (LFCS 2018) | 2018年 / 10703卷

关键词：

Modal logic; Completeness; Computational complexity; Bisimulation; COMPLEXITY; FORMULAS;

D O I：

10.1007/978-3-319-72056-2_1

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We introduce the completeness problem for Modal Logic and examine its complexity. For a definition of completeness for formulas, given a formula of a modal logic, the completeness problem asks whether the formula is complete for that logic. We discover that completeness and validity have the same complexity - with certain exceptions for which there are, in general, no complete formulas. To prove upper bounds, we present a non-deterministic polynomial-time procedure with an oracle from PSPACE that combines tableaux and a test for bisimulation, and determines whether a formula is complete.

引用

页码：1 / 21

页数：21

共 21 条

[1] When Are Prime Formulae Characteristic?
Aceto, L.
Della Monica, D.
Fabregas, I.
Ingolfsdottir, A.
[J]. MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2015, PT I, 2015, 9234 : 76 - 88
[2] Achilleos A., 2016, CORR
[3] Artemov S., 2015, 15 C LOGIC METHODOLO, P109
[4] Artemov S., 2016, SYNTACTIC EPISTEMIC
[5] Blackburn P., 2001, MODAL LOGIC, V53
[6] ON THE UNIQUE SATISFIABILITY PROBLEM
BLASS, A
GUREVICH, Y
[J]. INFORMATION AND CONTROL, 1982, 55 (1-3): : 80 - 88
[7] Chagrov A., 1997, Modal Logic
[8] DAgostino M., 1999, HDB TABLEAU METHODS, DOI [10.1007/978-94-017-1754-0, DOI 10.1007/978-94-017-1754-0]
[9] Fine K., 1975, Notre Dame Journal of Formal Logic, V16, P229, DOI 10.1305/ndjfl/1093891703
[10] Fitting Fit72 Melvin, 1972, Notre Dame Journal of Formal Logic, V13, P237

← 1 2 3 →