Computing with cylindric modal logics and arrow logics, lower bounds

被引：1
作者：
Marx M. [1 ]
机构：
[1] Language and Inference Technology, ILLC, Universiteit Van Amsterdam, 1018 WV Amsterdam
来源：
Studia Logica | 2002年 / 72卷 / 2期
关键词：
Arrow logic; Complexity; Cylindric algebras; Decidability; Finite model property; First order logic; Guarded fragment; Modal logic; Relation algebra;
D O I：
10.1023/A:1021360511488
中图分类号：
学科分类号：
摘要：
The complexity of the satisfiability problems of various arrow logics and cylindric modal logics is determined. As is well known, relativising these logics makes them decidable. There are several parameters that can be set in such a relativisation. We focus on the following three: the number of variables involved, the similarity type and the kind of relativised models considered. The complexity analysis shows the importance and relevance of these parameters. © 2002 Kluwer Academic Publishers.
引用
收藏
页码：233 / 252
页数：19
相关论文
共 17 条
  • [1] Andreka H., Hodkinson I., Nemeti I., Finite algebras of relations are representable on finite sets, Journal of Symbolic Logic, 64, pp. 243-267, (1999)
  • [2] Fisher M., Ladner R., Prepositional dynamic logic of regular programs, J. Comput. Syst. Sci., 18, pp. 194-211, (1979)
  • [3] Gradel E., On the restraining power of guards, Journal of Symbolic Logic, 64, pp. 1719-1742, (1999)
  • [4] Halpern J.Y., Moses Y.O., A guide to completeness and complexity for modal logics of knowledge and belief, Artificial Intelligence, 54, pp. 319-379, (1992)
  • [5] Ladner R., The computational complexity of provability in systems of modal prepositional logic, SIAM Journal of Computing, 6, pp. 467-480, (1977)
  • [6] Marx M., Mikulas Sz., Decidability of cylindric set algebras of dimension 2 and first order logic with two variables, Journal of Symbolic Logic, 64, pp. 1563-1572, (1999)
  • [7] Arrow Logic and Multimodal Logics, (1996)
  • [8] Marx M., Venema Y., Multi-dimensional Modal Logic, (1997)
  • [9] Mikulas Sz., Marx M., Undecidable relativizations of algebras of relations, Journal of Symbolic Logic, 64, pp. 747-760, (1999)
  • [10] Nemeti I., A Fine-Structure Analysis of First-order Logic, pp. 221-247
12