Belief revision within fragments of propositional logic

被引:19
作者
Creignou, Nadia [1 ]
Papini, Odile [2 ]
Pichler, Reinhard [3 ]
Woltran, Stefan [3 ]
机构
[1] Aix Marseille Univ, CNRS, LIF UMR 7279, F-13288 Marseille, France
[2] Aix Marseille Univ, CNRS, LSIS UMR 7296, F-13288 Marseille, France
[3] Vienna Univ Technol, Inst Informat Syst, A-1040 Vienna, Austria
基金
奥地利科学基金会;
关键词
Belief revision; Complexity; Fragments of propositional logic; KM postulates; KNOWLEDGE-BASE REVISION; COMPLEXITY; FRAMEWORK; UPDATE; SETS;
D O I
10.1016/j.jcss.2013.08.002
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Belief revision has been extensively studied in the framework of propositional logic, but just recently revision within fragments of propositional logic has gained attention. Hereby it is not only the belief set and the revision formula which are given within a certain language fragment, but also the result of the revision has to be located in the same fragment. So far, research in this direction has been mainly devoted to the Horn fragment of classical logic. Here we present a general approach to define new revision operators derived from known operators, such that the result of the revision remains in the fragment under consideration. Our approach is not limited to the Horn case but applicable to any fragment of propositional logic where the models of the formulas are closed under a Boolean function. Thus we are able to uniformly treat cases as dual Horn, Krom and affine formulas, as well. (C) 2013 Elsevier Inc. All rights reserved.
引用
收藏
页码:427 / 449
页数:23
相关论文
共 50 条
  • [31] Formula Synthesis in Propositional Dynamic Logic with Shuffle
    Pinchinat, Sophie
    Rubin, Sasha
    Schwarzentruber, Francois
    THIRTY-SIXTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FOURTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE / TWELVETH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, 2022, : 9902 - 9909
  • [32] On counting propositional logic and Wagner's hierarchy
    Antonelli, Melissa
    Dal Lago, Ugo
    Pistone, Paolo
    THEORETICAL COMPUTER SCIENCE, 2023, 966
  • [33] Circular (Yet Sound) Proofs in Propositional Logic
    Atserias, Albert
    Lauria, Massimo
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2023, 24 (03)
  • [34] Belief base rationalization for propositional merging
    Schwind, Nicolas
    Konieczny, Sebastien
    Marquis, Pierre
    JOURNAL OF LOGIC AND COMPUTATION, 2018, 28 (07) : 1601 - 1634
  • [35] Canonical Logic Programs Are Succinctly Incomparable with Propositional Formulas
    Shen, Yuping
    Zhao, Xishun
    FOURTEENTH INTERNATIONAL CONFERENCE ON THE PRINCIPLES OF KNOWLEDGE REPRESENTATION AND REASONING, 2014, : 665 - 668
  • [36] AUTOMATED REASONING USING POSSIBILISTIC LOGIC - SEMANTICS, BELIEF REVISION, AND VARIABLE CERTAINTY WEIGHTS
    DUBOIS, D
    LANG, J
    PRADE, H
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 1994, 6 (01) : 64 - 71
  • [37] Complexity of Model Checking for Cardinality-Based Belief Revision Operators
    Creignou, Nadia
    Ktari, Raida
    Papini, Odile
    SYMBOLIC AND QUANTITATIVE APPROACHES TO REASONING WITH UNCERTAINTY, ECSQARU 2017, 2017, 10369 : 387 - 397
  • [38] Iterated Belief Revision
    Stalnaker, Robert
    ERKENNTNIS, 2009, 70 (02) : 189 - 209
  • [39] Revocable Belief Revision
    Hans van Ditmarsch
    Studia Logica, 2013, 101 : 1185 - 1214
  • [40] Distributed Belief Revision
    Aldo Franco Dragoni
    Paolo Giorgini
    Autonomous Agents and Multi-Agent Systems, 2003, 6 : 115 - 143