Primal logic of information

07/12/2023
by   Yuri Gurevich, et al.
0

Primal logic arose in access control; it has a remarkably efficient (linear time) decision procedure for its entailment problem. But primal logic is a general logic of information. In the realm of arbitrary items of information (infons), conjunction, disjunction, and implication may seem to correspond (set-theoretically) to union, intersection, and relative complementation. But, while infons are closed under union, they are not closed under intersection or relative complementation. It turns out that there is a systematic transformation of propositional intuitionistic calculi to the original (propositional) primal calculi; we call it Flatting. We extend Flatting to quantifier rules, obtaining arguably the right quantified primal logic, QPL. The QPL entailment problem is exponential-time complete, but it is polynomial-time complete in the case, of importance to applications (at least to access control), where the number of quantifiers is bounded.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset