Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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.
https://hal.inria.fr/hal-01402046 Contributor : Hal IfipConnect in order to contact the contributor 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