Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102430
Title: Primal infon logic with conjunctions as sets
Authors: Cotrini, C.
Gurevich, Y.
Lahav, O.
Melentyev, A.
Issue Date: 2014
Publisher: Springer Verlag
Citation: Primal infon logic with conjunctions as sets / C. Cotrini, Y. Gurevich, O. Lahav, et al. — DOI 10.1007/978-3-662-44602-7_19 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2014. — Vol. 8705 LNCS. — P. 236-249.
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, (x ∧ y) → z does not entail (y ∧ x) → z, and similarly w → ((x ∧ y) ∧ z) does not entail w → (x ∧ (y ∧ z)). 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. © 2014 IFIP International Federation for Information Processing.
Keywords: COMPUTER SCIENCE
COMPUTERS
EXPECTED TIME
LINEAR TIME
MULTI-MODAL
NP-HARD
TRUST MANAGEMENT
ARTIFICIAL INTELLIGENCE
URI: http://hdl.handle.net/10995/102430
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84906766155
PURE ID: 365489
610a2f7c-4667-4f50-9106-77bc2748b608
ISSN: 3029743
ISBN: 9783662446010
DOI: 10.1007/978-3-662-44602-7_19
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84906766155.pdf569,02 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.