Skeptical Reasoning in FC-Normal Logic Programs is Π^1_1-complete
作者： Robert Saxon Milnikel
DOI:
关键词: Discrete mathematics 、 Mathematics 、 Computational logic 、 Dynamic logic (modal logic) 、 Philosophy of logic 、 Default logic 、 Programming language 、 Skepticism
摘要: FC-normal logic programs are a generalization by Marek, Nerode, and Remmel of Reiter's normal default theories. They have the property that, unlike most programs, they guaranteed to simple stable models. In this paper it is shown that problem skeptical reasoning in Π^1_1-complete, same complexity as for without restriction FC-normality. defined such way make testing program FC-normality very difficult general. A large subclass locally defined, be recursive, consequence expressive entire class programs.
kenyon.edu 参考文章(16)
J. W. Lloyd, Foundations of logic programming; (2nd extended ed.) Springer-Verlag New York, Inc.. ,(1987)
V. Wiktor Marek, Anil Nerode, Jeffrey B. Remmel, Complexity of Recursive Normal Default Logic Fundamenta Informaticae. ,vol. 32, pp. 139- 147 ,(1997) , 10.3233/FI-1997-32203
Vladimir Lifschitz, Michael Gelfond, Logic programs with classical negation international conference on lightning protection. pp. 579- 597 ,(1990)
John Wylie Lloyd, Foundations of logic programming ,(1984)
Dana S. Scott, Domains for Denotational Semantics international colloquium on automata, languages and programming. pp. 577- 613 ,(1982) , 10.1007/BFB0012801
Carl G. Jockusch, Robert I. Soare, Π⁰₁ classes and degrees of theories Transactions of the American Mathematical Society. ,vol. 173, pp. 33- 56 ,(1972) , 10.1090/S0002-9947-1972-0316227-0
Peter Cholak, Howard A. Blair, The Complexity Of Local Stratification Fundamenta Informaticae. ,vol. 21, pp. 333- 344 ,(1994) , 10.3233/FI-1994-2144
V.W. Marek, A. Nerode, J.B. Remmel, Logic programs, well-orderings and forward chaining Annals of Pure and Applied Logic. ,vol. 96, pp. 231- 276 ,(1999) , 10.1016/S0168-0072(98)00041-4
Robert Soare, Carl Jockusch, Degrees of members of $\Pi^0_1$ classes. Pacific Journal of Mathematics. ,vol. 40, pp. 605- 616 ,(1972) , 10.2140/PJM.1972.40.605
V. Wiktor Marek, Anil Nerode, Jeffrey B. Remmel, The Stable Models of a Predicate Logic Program Journal of Logic Programming. ,vol. 21, pp. 129- 154 ,(1994) , 10.1016/S0743-1066(14)80008-3