Skip to Main content Skip to Navigation
Conference papers

Primal Infon Logic with Conjunctions as Sets

Abstract : Primal infon logic was proposed by Gurevich and Neeman as an efficient yet expressive logic for policy and trust management. It is a propositional multimodal subintuitionistic logic decidable in linear time. However in that logic the principle of the replacement of equivalents fails. For example, $\left(x \land y\right) \to z$ does not entail $\left(y \land x\right) \to z$, and similarly $w \to \left(\left(x \land y\right)\land z\right)$ does not entail $w \to \left(x \land \left(y \land z\right)\right)$. Imposing the full principle of the replacement of equivalents leads to an NP-hard logic according to a recent result of Beklemishev and Prokhorov. In this paper we suggest a way to regain the part of this principle restricted to conjunction: We introduce a version of propositional primal logic that treats conjunctions as sets, and show that the derivation problem for this logic can be decided in linear expected time and quadratic worst-case time.
Document type :
Conference papers
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/hal-01402046
Contributor : Hal Ifip <>
Submitted on : Thursday, November 24, 2016 - 10:52:01 AM
Last modification on : Thursday, May 27, 2021 - 1:54:06 PM
Long-term archiving on: : Tuesday, March 21, 2017 - 9:59:20 AM

File

978-3-662-44602-7_19_Chapter.p...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Carlos Cotrini, Yuri Gurevich, Ori Lahav, Artem Melentyev. Primal Infon Logic with Conjunctions as Sets. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. pp.236-249, ⟨10.1007/978-3-662-44602-7_19⟩. ⟨hal-01402046⟩

Share

Metrics

Record views

136

Files downloads

271