A general framework for computing maximal contractions

doi:10.1007/s11704-012-2044-8

Front Comput Sci

2013, Vol. 7

Issue (1) : 83-94 https://doi.org/10.1007/s11704-012-2044-8

RESEARCH ARTICLE

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

Download: PDF(1203 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Cite this article:

Jie LUO. A general framework for computing maximal contractions[J]. Front Comput Sci, 2013, 7(1): 83-94.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-012-2044-8
https://academic.hep.com.cn/fcs/EN/Y2013/V7/I1/83

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

[1]	Shuaiqiang WANG, Yilong YIN. Polygene-based evolutionary algorithms with frequent pattern mining[J]. Front. Comput. Sci., 2018, 12(5): 950-965.
[2]	Yong WANG, Zhi-Zhong LIU, Jianbin LI, Han-Xiong LI, Jiahai WANG. On the selection of solutions for mutation in differential evolution[J]. Front. Comput. Sci., 2018, 12(2): 297-315.
[3]	Quanjun YIN, Long QIN, Yong PENG, Wei DUAN. Learning real-time search on c-space GVDs[J]. Front. Comput. Sci., 2017, 11(6): 1036-1049.
[4]	Yingying ZHU,Cong YAO,Xiang BAI. Scene text detection and recognition: recent advances and future trends[J]. Front. Comput. Sci., 2016, 10(1): 19-36.
[5]	Silvano COLOMBO TOSATTO,Pierre KELSEN,Qin MA,Marwane el KHARBILI,Guido GOVERNATORI,Leendert van der TORRE. Algorithms for tractable compliance problems[J]. Front. Comput. Sci., 2015, 9(1): 55-74.
[6]	Hebah ELGIBREEN,Mehmet Sabih AKSOY. RULES-IT: incremental transfer learning with RULES family[J]. Front. Comput. Sci., 2014, 8(4): 537-562.
[7]	Chaoqun LI,Liangxiao JIANG,Hongwei LI. Naive Bayes for value difference metric[J]. Front. Comput. Sci., 2014, 8(2): 255-264.
[8]	Dunwei GONG, Yan ZHANG. Generating test data for both path coverage and fault detection using genetic algorithms[J]. Front Comput Sci, 2013, 7(6): 822-837.
[9]	Dongchen JIANG, Wei LI, Jie LUO, Yihua LOU, Zhengzhong LIAO. A decomposition based algorithm for maximal contractions[J]. Front Comput Sci, 2013, 7(6): 801-811.
[10]	Pablo RABANAL, Ismael RODRíGUEZ, Fernando RUBIO. An ACO-RFD hybrid method to solve NP-complete problems[J]. Front Comput Sci, 2013, 7(5): 729-744.
[11]	Hongli YANG, Chao CAI, Liyang PENG, Xiangpeng ZHAO, Zongyan QIU, Shengchao QIN. Algorithms for checking channel passing in web service choreography[J]. Front Comput Sci, 2013, 7(5): 710-728.
[12]	Yi WANG, Renfa LI. FPGA based unified architecture for public key and private key cryptosystems[J]. Front Comput Sci, 2013, 7(3): 307-316.
[13]	Bo YUAN, Wenhuang LIU. Measure oriented training: a targeted approach to imbalanced classification problems[J]. Front Comput Sci, 2012, 6(5): 489-497.
[14]	Min XIE, Laks V. S. LAKSHMANAN, Peter T. WOOD. Composite recommendations: from items to packages[J]. Front Comput Sci, 2012, 6(3): 264-277.
[15]	Fabian GIESEKE, Gabriel MORUZ, Jan VAHRENHOLD. Resilient k-d trees: k-means in space revisited[J]. Front Comput Sci, 2012, 6(2): 166-178.

Viewed

Full text

Abstract

Cited

Shared

Discussed