Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 5 of 5
Full-Text Articles in Physical Sciences and Mathematics
Embedding Modal Nonmonotonic Logics Into Default Logic, Robert Milnikel
Embedding Modal Nonmonotonic Logics Into Default Logic, Robert Milnikel
Robert Milnikel
We present a straightforward embedding of modal nonmonotonic logics into default logic.
Derivability In Certain Subsystems Of The Logic Of Proofs Is -Complete, Robert Milnikel
Derivability In Certain Subsystems Of The Logic Of Proofs Is -Complete, Robert Milnikel
Robert Milnikel
The Logic of Proofs realizes the modalities from traditional modal logics with proof polynomials , so an expression □F becomes t:F where t is a proof polynomial representing a proof of or evidence for F. The pioneering work on explicating the modal logic S4 is due to S. Artemov and was extended to several subsystems by V. Brezhnev. In 2000, R. Kuznets presented a algorithm for deducibility in these logics; in the present paper we will show that the deducibility problem is-complete. (The analogous problem for traditional modal logics is PSPACE-complete.) Both Kuznets’s work and the present results make assumptions …
Skeptical Reasoning In Fc-Normal Logic Programs Is Π^1_1-Complete, Robert Milnikel
Skeptical Reasoning In Fc-Normal Logic Programs Is Π^1_1-Complete, Robert Milnikel
Robert Milnikel
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 logic programs, they are guaranteed to have simple stable models. In this paper it is shown that the problem of skeptical reasoning in FC-normal programs is Π^1_1-complete, the same complexity as for logic programs without the restriction of FC-normality. FC-normal programs are defined in such a way as to make testing a program for FC-normality very difficult in general. A large subclass of FC-normal programs, locally FC-normal programs, is defined, shown to be recursive, and shown to …
Sequent Calculi For Skeptical Reasoning In Predicate Default Logic And Other Nonmonotonic Logics, Robert Milnikel
Sequent Calculi For Skeptical Reasoning In Predicate Default Logic And Other Nonmonotonic Logics, Robert Milnikel
Robert Milnikel
Sequent calculi for skeptical consequence in predicate default logic, predicate stable model logic programming, and infinite autoepistemic theories are presented and proved sound and complete. While skeptical consequence is decidable in the finite propositional case of all three formalisms, the move to predicate or infinite theories increases the complexity of skeptical reasoning to being Π 1 1 -complete. This implies the need for sequent rules with countably many premises, and such rules are employed.
The Complexity Of Predicate Default Logic Over A Countable Domain, Robert Milnikel
The Complexity Of Predicate Default Logic Over A Countable Domain, Robert Milnikel
Robert Milnikel
Lifschitz introduced the notion of defining extensions of predicate default theories not as absolute, but relative to a specified domain. We look specifically at default theories over a countable domain and show the set of default theories which possess an ω-extension is Σ21-complete. That the set is in Σ21 is shown by writing a nearly circumscriptive formula whose ω-models correspond to the ω-extensions of a given default theory; similarly, Σ21-hardness is established by a method for translating formulas into default theories in such a way that ω-models of the circumscriptive formula correspond to ω-extensions of the default theory. (That the …