Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8904328 | Journal of Applied Logic | 2017 | 26 Pages |
Abstract
Input/output logic is a formalism in deontic logic and normative reasoning. Unlike deontic logical frameworks based on possible-world semantics, input/output logic adopts norm-based semantics in the sense of [13], specifically operational semantics. It is well-known in theoretical computer science that complexity is an indispensable component of every logic. So far, previous literature in input/output systems focuses on proof theory and semantics, while neglects complexity. This paper adds the missing component by giving the complexity results of main decision problems in input/output logic. Our results show that input/output logic is coNP hard and in the 2nd level of the polynomial hierarchy.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Logic
Authors
Xin Sun, Livio Robaldo,