Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6876332 | Theoretical Computer Science | 2013 | 17 Pages |
Abstract
We extend the methodology in Baaz and Fermüller (1999) [5] to systematically construct analytic calculi for semi-projective logics-a large family of (propositional) locally finite many-valued logics. Our calculi, defined in the framework of sequents of relations, are proof search oriented and can be used to settle the computational complexity of the formalized logics. As a case study we derive sequent calculi of relations for Nilpotent Minimum logic and for Hajek's Basic Logic extended with the n-contraction axiom (nâ¥1). The introduced calculi are used to prove that the decidability problem in these logics is Co-NP complete.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Agata Ciabattoni, Franco Montagna,