|
|
A general framework for computing maximal contractions |
Jie LUO( ) |
State Key Laboratory of Software Development Environment, School of Computer Science and Engineering, Beihang University, Beijing 100191, China |
|
|
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
|
Corresponding Author(s):
LUO Jie,Email:luojie@nlsde.buaa.edu.cn
|
Issue Date: 01 February 2013
|
|
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 doi: 10.2307/2274239
|
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 doi: 10.1007/3-540-44491-2_42
|
4 |
Li W. A development calculus for specifications. Science in China Series F: Information Sciences , 2003, 46(5): 390-400 doi: 10.1360/02ye0122
|
5 |
Li W. R-calculus: an inference system for belief revision. The Computer Journal , 2007, 50(4): 378-390 doi: 10.1093/comjnl/bxl069
|
6 |
Li W. Logical verification of scientific discovery. Science in China Series F: Information Sciences , 2010, 53(4): 677-684 doi: 10.1007/s11432-010-0084-y
|
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 doi: 10.1007/s11432-011-4492-4
|
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 doi: 10.1007/s11432-010-4172-9
|
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 doi: 10.1016/0004-3702(92)90018-S
|
16 |
Delgrande J P, Schaub T. A consistency-based approach for belief change. Artificial Intelligence , 2003, 151(1): 141 doi: 10.1016/S0004-3702(03)00111-5
|
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 doi: 10.1093/logcom/14.6.801
|
18 |
Gallier J H. Logic for Computer Science: Foundations of Automatic Theorem Proving. New York: Harper & Row, 1985
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|