Computing with Cylindric Modal Logics and Arrow Logics,Lower Bounds |
| |
| Authors: | Marx Maarten |
| |
| Affiliation: | (1) Language and Inference Technology, ILLC, Universiteit van Amsterdam, Nieuwe Achtergracht 166, 1018 WV Amsterdam, The Netherlands |
| |
| Abstract: | 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. |
| |
| Keywords: | modal logic arrow logic cylindric algebras relation algebra first order logic guarded fragment decidability complexity finite model property |
| 本文献已被 SpringerLink 等数据库收录！ |
|
