Syntactic Representations of Semantic Merging Operations

Recent research suggests the usefulness of conducting information merging on the level of epistemic states as an alternative to the usual approach of knowledge base merging [1,2]. We take an epistemic state to be an assignment of natural numbers to the classical valuations of the finite propositional logic under consideration. In this paper we investigate various syntactic representations of epistemic states and show how these can be employed to represent merging operations syntactically. These include ranked knowledge bases and their normals forms, as well as different versions of structures referred to as partitions. We show that there are efficient methods for transformaing any ranked knowledge base into an equivalent partition, and vice versa. We provide a uniform method for obtaining syntactic representations, in terms of partitions, of a large class of semantic merging operations. This method is linear in n times the product of the sizes of the n partitions used to represent the epistemic states to be merged. For the class of lexicographic merging operations, it can be proved that this method represents the best we can do in terms of computational complexity. We also show that the structure of some semantic merging operations can be exploited to obtain syntactic representations for them which can be determined much more efficiently than the uniform method provided. To be able to use these efficient methods, it is necessary to use ranked knowledge bases as the syntactic representational form.

Authors and Affiliations

1. Department of Computer Science, University of Pretoria, Pretoria, 0002, South Africa

   Thomas Meyer

2. Decision Systems Laboratory School of Information Technology and Computer Science, University of Wollongong, Wollongong, NSW, 2522, Australia

   Aditya Ghose

3. Knowledge Systems Group, School of Computer Science and Engineering, University of New South Wales, Sydney, NSW, 2052, Australia

   Samir Chopra

Editors and Affiliations

1. School of Information Science and Technology Department of Information and Communication Engineering, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo, 113-8656, Japan

   Mitsuru Ishizuka

2. School of Information Technology Knowledge Representation and Reasoning Unit (KRRU) Faculty of Engineering and Information Technology, Griffith University, PMB 50 Gold Coast Mail Centre, Queensland, 9726, Australia

   Abdul Sattar

Reprints and permissions

© 2002 Springer-Verlag Berlin Heidelberg

Policies and ethics