On the decidability of open logic. (English) Zbl 1191.03006
Summary: Open Logic (OL) is a noticeable logic theory dealing with the description of knowledge growth and updating, as well as the evolution of hypotheses. Up to now, however, many problems related to the proof-theoretical approach of OL remain to be explored. In this paper, the typical proof-theoretical problems for OL are described and the concept of open proof is defined. Two major conclusions are as follows: (i) For the consistent OL systems, the open proof problem is semi-decidable (a decision algorithm is presented). (ii) For general (normal, not necessarily consistent) OL systems, the open proof problem is not semi-decidable.
References:
| [1] | Reiter R. A logic for default reasoning. Artif Intel, 1980, 13: 81–132 · Zbl 0435.68069 · doi:10.1016/0004-3702(80)90014-4 |
| [2] | Li W. An open logic system (in Chinese). Sci China Ser A. 1992, (10): 1103–1113 |
| [3] | Li W. A logical framework for inductive inference and its rationality. In: Proceedings of the 12th Australian Joint Conference on Artificial Intelligence: Advanced Topics in Artificial Intelligence. London: Springer-Verlag, 1999. 304–315 · Zbl 0952.03027 |
| [4] | Li W, Ma S, Sui Y, et al. A logical framework for convergent infinite computations. CoRR cs.LO/0105020. 2001 |
| [5] | Ma S, Sui Y, Xu K. The limits of Horn logic programs. In: Proceedings of 18th International Conference on Logic Programming (ICLP), Denmark, LNCS 2401. Berlin: Springer-Verlag, 2002. 467–478. Full paper available as CoRR cs. LO/0103008: (2001). |
| [6] | Li W. R-calculus: an inference system for belief revision. Comput J. 2007, 50(4): 378–390 · doi:10.1093/comjnl/bxl069 |
| [7] | Su K, Li W. Computation of extensions of seminormal default theories. Fund Infor. 1999, 40(1): 79–102 · Zbl 0945.68162 |
| [8] | Luan S M, Dai G Z, Li W. A programmable approach to revising knowledge base. Sci China Ser F-Inf Sci. 2005, 48(6): 681–692 · Zbl 1161.68788 · doi:10.1360/03yf0327 |
| [9] | Li W, Zhang Y. An abstract logic for epistemic processes description (in Chinese). Sci China Ser E. 1996. 26: 168–178 |
| [10] | Huai J, Li W. An open default theory. Chinese J Comput. 1994, 17: 652–661 |
| [11] | Davis M. Computability Complexity and Language. New York: Academic Press, 1983 · Zbl 0569.68042 |
| [12] | Davis M. Computability and Unsolvability. New York: McGraw-Hill, 1958 |
| [13] | Zhu W, Xiao X. Introduction to Set Theory. Nanjing: Nanjing Univ. Press, 1991. 87–126 |
| [14] | Chang C L, Lee C T L. Symbolic Logic and Mechanical Theorem Proving. New York: Academic Press, 1973 · Zbl 0263.68046 |
| [15] | Zhang W. Inference ability comparison of some incomplete strategies. In: Proceedings of ICYCS’95. Beijing: Beijing University Press, 1995. 1: 542–547 |
| [16] | Zhang W. Verification of real-time programs by knowledge based strategy. Dissertation for the Doctoral Degree. Shenyang: Northeastern University, 1992. 23–50 |
| [17] | Li W. Mathematical Logic: Principles and Formal Calculus (in Chinese). Beijing: Science Press, 2008. 45–184 |
| [18] | Liu X. Fuzzy Logic and Fuzzy Reasoning (in Chinese). Changchun: Jilin University Press, 1989. 117–123 |
| [19] | Wang S, Liu D. The complexity of open logic based on totalordered partition model (in Chinese). J Comput Res Develop. 2002, 10: 1244–1247 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
