Peter Z. Revesz
ABSTRACT
Katsuno and Mendelzon divide theory change, the problem of adding new information to a logical theory, into two types: revision and update. We propose a third type of theory change: arbitration. The key idea is the following: the new information is considered neither better nor worse than the old information represented by the logical theory. The new information is simply one voice against a set of others already incorporated into the logical theory. From this follows that arbitration should be commutative. First we define arbitration by a set of postulates and then describe a model-theoretic characterization of arbitration for the case of propositional logical theories. We also study weighted arbitration where different models of a theory can have different weights.
- AG85.S. Abiteboul & G. Grahne. Update semantics for incomplete databases. Proceedings of the Eleventh International Conference on Very Large Databases, 1-12, 1985.Google Scholar
- ASV90.S. Abiteboul, E. Simon & V. Vianu. Non-deterministic languages to express deterministic transformations. Proceedings of the Ninth A CM SIGA CT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 218-229, 1990. Google ScholarDigital Library
- AGM85.C.E. Alchourr6n, P. G#rdenfors & D. Makinson. On the logic of theory change: partial meet contraction and revision functions. Journal of Symbolic Logic, (50) 510-530, 1985.Google Scholar
- BS81.F. Bancilhon & N. Spyratos. Update semantics of relational views. A CM Transactions on Database Systems, (4) 557-575, 1981. Google ScholarDigital Library
- Bor85.A.Borgida. Language features for flexible handling of exceptions in information systems. A CM Transaction on Database Systems, 10, pages 563- 603, 1985. Google ScholarDigital Library
- Dal88.M. Dalai. Investigations into a theory of knowledge base revision: Preliminary report. Proceedings of the AAAI, pages 475-479, 1988.Google Scholar
- EG92.T. Eiter & G. Gottlob. On the complexity of propositional knowledge base revision, updates, and eounterfactuals. Proceedings of the Eleventh A CM SIGA CT-SIGMOD- SIGART Symposium on Principles of Database Systems, pages 261-273, 1992. Google ScholarDigital Library
- FUV83.It. Fagin, J. D. Ullman & M. Y. Vardi. On the semantics of updates in databases. Proceedings of t he Second A CM SIGA CT-SIGMOD- SIGART Symposium on Principles of Database Systems, pages 352-365, 1983. Google ScholarDigital Library
- Gär88.P. GKrdenfors. Knowledge in Fluz: Modeling the Dynamics of Epistemic States. Bradford Books, MIT Press, Cambridge, MA, 1988.Google Scholar
- GMR92.G. Grahne, A. O. Mendelzon, & P. Z. Revesz. Knowledsebase #~axtst#ormations. Proceedings of the Eleventh A CM $1GA CT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 246-260, 1992. Google ScholarDigital Library
- KW85.A.M. Keller & M. Winslett Wilkins. On the use of an extended relational model to handle changing incomplete information. IEEE Trans. on Software Engineering, 11:7, pages 620- 633, 1985.Google ScholarDigital Library
- KM89.H. Katsuno & A. O. Mendelzon. A unified view of propositional knowledge base updates. Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, pages 1413-1419, 1989.Google Scholar
- KM91.H. Katsuno & A. O. Mendelzon. On the difference between updating a knowledge base and revising it. Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning, pages 387-394, 1991.Google ScholarDigital Library
- KM91.H. Katsuno & A. O. Mendelzon. Propositional knowledge base revision and minimal change. Artificial Intelligence, 52, pages 263-294, 1991. Google ScholarDigital Library
- KM92.H. Katsuno & A. O. Mendelzon. On the difference between updating a knowledge-base and revising it. manuscript.Google Scholar
- McC68.J. McCarthy. Programs with common sense. In: M. Minsky, (Ed.), Semantic Information Processing, M-IT Press, Cambridge, MA, pages 403-418, 1968.Google Scholar
- Mak85.D.Makinson. How to give it up: A survey of some formal aspects of the logic of theory change. Synth#se, (62) 347-363, 1985Google Scholar
- Rei92.It. Reiter. On specifying database updates. Proceedings of the Third In. ternational Conference on Eztending Database Technology, 1992.Google Scholar
- Rei78.R. Reiter. On closed world databases. In: Logic and Databases, H. Gallaire & J. Minker, editors. Plenum Press, New York, pages 55-76, 1978.Google Scholar
- Sat88.K. Satoh. Nonmonotonic reasoning by minimal belief revision. Proceedings International Conference on Fifth Generation Systems, pages 455-462, 1988.Google Scholar
- Web86.A. Weber. Updating propositional formulas. Proceedings First Conference on Ezpert Database Systems, pages 487-500, 1986.Google Scholar
- Win88.M. Winslett. Reasoning about action using a possible models approach. Proceedings of the Seventh National Conference on Artificial Intelligence, pages 89-93, 1988.Google ScholarDigital Library
- Zad78.L.A. Zadeh. Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets and Systems, pages 3-28, 1978.Google ScholarCross Ref
Index Terms
- On the semantics of theory change: arbitration between old and new information
Recommendations
On the Logic of Theory Change: Contraction without Recovery
The postulate of Recovery, among the six postulates for theory contraction, formulated and studied by Alchourrón, Gärdenfors and Makinson is the one that has provoked most controversy. In this article we construct withdrawal functions that do not satisfy ...
Infobase Change: A First Approximation
Generalisations of theory change involving operations on arbitrary sets of wffs instead of on belief sets (i.e., sets closed under a consequence relation), have become known as base change. In one view, a base should be thought of as providing more ...
Four Floors for the Theory of Theory Change: The Case of Imperfect Discrimination
Proceedings of the 14th European Conference on Logics in Artificial Intelligence - Volume 8761The theory of theory change due to Alchourrón, Gärdenfors and Makinson ("AGM") has been widely known as being characterised by two packages of postulates. The basic package consists of six postulates and is very weak, the full package adds two further ...
Reviews
Vasant B. Kaujalgi
Theory of change is relevant to databases, artificial intelligence, and belief revision. General rules for updating are difficult for large heterogeneous databases. Logical theory is complex for such databases, particularly when views and integrity constraints are taken into account. The author proposes arbitration as the third type of theory of change, in addition to the two existing types, namely revision and update. Arbitration is defined in terms of model fitting. The author proposes axioms for arbitration similar to the axioms for revision and update that are included in the appendix of the paper. He extends the arbitration concepts to models of databases with different weights. The paper ends with a few research topics. The examples in the paper help explain the concepts of arbitration. This paper is a definite contribution to semantic information processing and knowledge base transformation. It will be of great interest to researchers and doctoral students in these fields. Particularly, the open questions and references in the paper may lead to research topics.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments