Belief merging in Dynamic Logic of Propositional Assignments

Andreas Herzig (1, 2) , Pilar Pozos Parra (3) , François Schwarzentruber (4)

1 IRIT-LILaC - Logique, Interaction, Langue et Calcul
2 CNRS - Centre National de la Recherche Scientifique
3 Universidad Juarez Autonoma Tabasco, Mexico
4 LogicA - Logic and Applications

We study syntactical merging operations that are defined semantically by means of the Hamming distance between valuations; more precisely, we investigate the Σ-semantics, Gmax-semantics and max-semantics. We work with a logical language containing merging operators as connectives, as opposed to the metalanguage operations of the literature. We capture these merging operators as programs of Dynamic Logic of Propositional Assignments DL-PA. This provides a syntactical characterisation of the three semantically defined merging operators, and a proof system for DL-PA therefore also provides a proof system for these merging operators. We explain how PSPACE membership of the model checking and satisfiability problem of star-free DL-PA can be extended to the variant of DL-PA where symbolic disjunctions that are parametrised by sets (that are not defined as abbreviations, but are proper connectives) are built into the language. As our merging operators can be polynomially embedded into this variant of DL-PA, we obtain that both the model checking and the satisfiability problem of a formula containing possibly nested merging operators is in PSPACE.

Mots clés: Dynamic logic; Belief merging; Belief change

Domaines: Intelligence artificielle [cs.AI]; Apprentissage [cs.LG]; Logique en informatique [cs.LO]; Informatique et langage [cs.CL]; Recherche d'information [cs.IR]

Andreas Herzig, Pilar Pozos Parra, François Schwarzentruber. Belief merging in Dynamic Logic of Propositional Assignments. International Symposium on Foundations of Information and Knowledge Systems - FolKS 2014, Mar 2014, Bordeaux, France. pp. 981-398. ⟨hal-01146747⟩