A general framework for computing maximal contractions

Abstract

This paper investigates the problem of computing all maximal contractions of a given formula set Γ with respect to a consistent set Δ of atomic formulas and negations of atomic formulas. We first give a constructive definition of minimal inconsistent subsets and propose an algorithmic framework for computing all minimal inconsistent subsets of any given formula set. Then we present an algorithm to compute all maximal contractions fromminimal inconsistent subsets. Based on the algorithmic framework and the algorithm, we propose a general framework for computing all maximal contractions. The computability of the minimal inconsistent subset and maximal contraction problems are discussed. Finally, we demonstrate the ability of this framework by applying it to the first-order language without variables and design an algorithmfor the computation of all maximal contractions.

Keywords

maximal contraction / minimal inconsistent subset / computability / algorithms

References

[1] Alchourrón C, Gärdenfors P, Makinson D. On the logic of theory change: partial meet contraction and revision functions. Journal of Symbolic Logic, 1985, 50(2): 510-530

[2] Li W. A logical framework for evolution of specifications. In: Proceedings of the 5th European Symposium on Programming: Programming Languages and Systems, ESOP ’94. 1994, 394-408

[3] Li W. A computational framework for convergent agents. In: Leung K, Chan L W, Meng H, eds. Intelligent Data Engineering and Automated Learning- IDEAL 2000. Data Mining, Financial Engineering, and Intelligent Agents. Berlin / Heidelberg: Springer, 2000, 113-126

[4] Li W. A development calculus for specifications. Science in China Series F: Information Sciences, 2003, 46(5): 390-400

[5] Li W. R-calculus: an inference system for belief revision. The Computer Journal, 2007, 50(4): 378-390

[6] Li W. Logical verification of scientific discovery. Science in China Series F: Information Sciences, 2010, 53(4): 677-684

[7] Li W. Mathematical Logic: Foundations for Information Science, 1st ed. Basel: Bikhäuser, 2010

[8] Luo J, Li W. R-calculus without the cut rule. Science in China Series F: Information Sciences, 2011, 54(12): 2530-2543

[9] Li H, Li L. Computing R-contraction for propositional logic is hard. In: Proceedings of the 2nd International Workshop on Education Technology and Computer Science. 2010, 260-263

[10] Jiang D, Lou Y, Jin Y. A revision system based on delegate model for propositional logic. In: Proceedings of the 2nd International Conference on Information Engineering and Computer Science. 2009, 1-4

[11] Jiang D, Lou Y, Jin Y. A revision approach based on assignment equivalence classes. In: Proceedings of the 2nd International Workshop on Intelligent Systems and Applications. 2010, 1-4

[12] Luo J, Li W. An algorithm to compute maximal contractions for Horn clauses. Science in China Series F: Information Sciences, 2011, 54(2): 244-257

[13] Nebel B. Belief revision and default reasoning: syntax-based approaches. In: Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning. 1991, 417-428

[14] Nebel B. Base revision operations and schemes: semantics representation, and complexity. In: Proceedings of the 11th European Conference on Artificial Intelligence. 1994, 341-345

[15] Eiter T, Gottlob G. On the complexity of propositional knowledge base revision, updates, and counterfactuals. Artificial Intelligence, 1992, 57(2-3): 227-270

[16] Delgrande J P, Schaub T. A consistency-based approach for belief change. Artificial Intelligence, 2003, 151(1): 141

[17] Delgrande J P, Schaub T, Tompits H, Woltran S. On computing belief change operations using quantified boolean formulas. Journal of Logic and Computation, 2004, 14(6): 426-438

[18] Gallier J H. Logic for Computer Science: Foundations of Automatic Theorem Proving. New York: Harper & Row, 1985

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg