Abstract
Complexity of provability and satisfiability problems in many non-classical logics, for instance, in intuitionistic logic, various systems of modal logic, temporal and dynamic logics was studied in [3,5,9,22-24]. Ladner [9] proved that the provability problem is PSPACE-complete for modal logics K, T and S4 and coNP-complete for S5. Statman [24] proved that the problem of determining if an arbitrary implicational formula is intuitionistically valid is PSPACE-complete. We consider the complexity of some properties for non-classical logics which are known to be decidable. The complexity of tabularity, pre-tabularity, and interpolation problems in extensions of the intuitionistic logic and of the modal logic S4 is studied, as well as the complexity of amalgamation problems in varieties of Heyting algebras and closure algebras. © Springer-Verlag Berlin Heidelberg 2003.
| Original language | English |
|---|---|
| Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci. |
| Publisher | Springer Nature |
| Pages | 397-412 |
| Number of pages | 15 |
| Volume | 2803 |
| Publication status | Published - 2003 |
| Event | Computer Science Logic, 17th International Workshop, CSL 2003, 12th Annual Conference of the EACSL, and 8th Kurt Gödel Colloquium, KGC 2003, Vienna, Austria, August 25-30, 2003, Proceedings - Duration: 1 Jan 1824 → … http://dblp.uni-trier.de/db/conf/csl/csl2003.html#RybinaV03http://dblp.uni-trier.de/rec/bibtex/conf/csl/RybinaV03.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/csl/RybinaV03 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|
Conference
| Conference | Computer Science Logic, 17th International Workshop, CSL 2003, 12th Annual Conference of the EACSL, and 8th Kurt Gödel Colloquium, KGC 2003, Vienna, Austria, August 25-30, 2003, Proceedings |
|---|---|
| Period | 1/01/24 → … |
| Internet address |