An elementary construction for a non-elementary procedure

被引：2

作者：

Marx M. ^{[1
]}

Mikulás S. ^{[2
]}

机构：

[1] Language and Inference Technology Group, ILLC, Universiteit Van Amsterdam, 1018 WV Amsterdam

[2] School of Computer Science and Information Systems, Birkbeck College, University of London, London WC1E 7HX, Malet Street

来源：

Studia Logica | 2002年 / 72卷 / 2期

关键词：

Decidability; Finite model property; Modal logic; Product of modal logics;

D O I：

10.1023/A:1021312628326

中图分类号：

学科分类号：

摘要：

We consider the problem of the product finite model property for binary products of modal logics. First we give a new proof for the product finite model property of the logic of products of Kripke frames, a result due to Shehtman. Then we modify the proof to obtain the same result for logics of products of Kripke frames satisfying any combination of seriality, reflexivity and symmetry. We do not consider the transitivity condition in isolation because it leads to infinity axioms when taking products. © 2002 Kluwer Academic Publishers.

引用

页码：253 / 263

页数：10

共 17 条

[1]

Blackburn P., De Rijke M., Venema Y., Modal Logic, (2001)

[2]

Fagin R., Halpern J.Y., Moses Y., Vardi M.Y., Reasoning about Knowledge, (1995)

[3]

Gabbay D., Shehtman V., Products of modal logics, part 1, Logic Journal of the IGPL, 6, pp. 73-146, (1998)

[4]

Gabbay D., Shehtman V., Products of modal logics, part 2, Logic Journal of the IGPL, 8, pp. 165-210, (2000)

[5]

Gabbay D., Kurucz A., Wolter F., Zakharyaschev M., Many-Dimensional Modal Logics: Theory and Applications

[6]

Gradel E., Kolaitis P., Vardi M., On the decision problem for two-variable first order logic, Bulletin of Symbolic Logic, 3, pp. 53-69, (1997)

[7]

Marx M., Complexity of products of modal logics, Journal of Logic and Computation, 9, pp. 221-238, (1999)

[8]

Marx M., Mikulas Sz., Decidability of cylindric set algebras of dimension two and first-order logic with two variables, Journal of Symbolic Logic, 64, pp. 1563-1572, (1999)

[9]

Marx M., Mikulas Sz., Products, or how to create modal logics of high complexity, Logic Journal of the IGPL, 9, pp. 77-88, (2001)

[10]

Reynolds M., A decidable logic of parallelism, Notre Dame Journal of Formal Logic, 38, pp. 419-436, (1997)

← 1 2 →