Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 8 of 8
Full-Text Articles in Physical Sciences and Mathematics
General Model Theoretic Semantics For Higher-Order Horn Logic Programming, Mino Bai, Howard A. Blair
General Model Theoretic Semantics For Higher-Order Horn Logic Programming, Mino Bai, Howard A. Blair
Electrical Engineering and Computer Science - Technical Reports
We introduce model-theoretic semantics [6] for Higher-Order Horn logic programming language. One advantage of logic programs over conventional non-logic programs has been that the least fixpoint is equal to the least model, therefore it is associated to logical consequence and has a meaningful declarative interpretation. In simple theory of types [9] on which Higher-Order Horn logic programming language is based, domain is dependent on interpretation [10]. To define T p operator for a logic program P, we need a fixed domain without regard to interpretation which is usually taken to be a set of atomic propositions. We build a semantics …
The Expressiveness Of Locally Stratified Programs, Howard A. Blair, Wiktor Marek, John S. Schlipf
The Expressiveness Of Locally Stratified Programs, Howard A. Blair, Wiktor Marek, John S. Schlipf
Electrical Engineering and Computer Science - Technical Reports
This paper completes an investigation of the logical expressibility of finite, locally stratified, general logic programs. We show that every hyperarithmetic set can be computed by a suitably chosen locally stratified logic program (as a set of values of a predicate over its perfect model). This is an optimal result, since the perfect model of a locally stratified program is itself an implicitly definable hyperarithmetic set (under a recursive coding of the Herbrand base); hence to obtain all hyperarithmetic sets requires something new, in this case selecting one predicate from the model. We find that the expressive power of programs …
The Complexity Of Local Stratification, Peter Cholak, Howard A. Blair
The Complexity Of Local Stratification, Peter Cholak, Howard A. Blair
Electrical Engineering and Computer Science - Technical Reports
The class of locally stratified logic programs is shown to be Π11-complete by the construction of a reducibility of the class of infinitely branching nondeterministic finite register machines.nondeterministic finite register machines.
A Unified Framework For Three-Valued Semantical Treatments Of Logic Programming, Feng Yang
A Unified Framework For Three-Valued Semantical Treatments Of Logic Programming, Feng Yang
Electrical Engineering and Computer Science - Technical Reports
Based on Fiting's Φ operator a unified framework for three-valued semantics of logic programming is presented. The truth space used in the framework is the class of partial interpretations. Underlying the truth space is two partial orderings, knowledge ordering and truth ordering. It turns out that the truth space with the truth ordering is a complete lattice and the truth space with knowledge ordering is a semi-complete lattice. Φ is proved to be continuous over the complete lattice and monotonic over the semi-complete lattice. With the use of Φ operator two well-known three-valued semantics for logic programming, Fitting's three-valued semantics …
Duality In Logic Programming, Feng Yang
Duality In Logic Programming, Feng Yang
Electrical Engineering and Computer Science - Technical Reports
Various approximations of classic negation have been proposed for logic programming. But the semantics for those approximations are not entirely clear. In this paper a proof-theoretic operator, we call it failure operator, denoted as FP, is associated with each logic program to characterize the meaning of various negations in logic programming. It is shown that the failure operator FP is a dual of the TP, immediate consequence operator developed by Van Emden and Kowalski and is downward continuous. It has the desirable properties entirely analogous to what TP has such as continuity, having a unique least fixpoint and a unique …
Monotone Logic Programming, Howard A. Blair, Allen Brown Jr., V. S. Subrahmanian
Monotone Logic Programming, Howard A. Blair, Allen Brown Jr., V. S. Subrahmanian
Electrical Engineering and Computer Science - Technical Reports
We propose a notion of an abstract logic. Based on this notion, we define abstract logic programs to be sets of sentences of an abstract logic. When these abstract logics possess certain logical properties (some properties considered are compactness, finitariness, and monotone consequence relations) we show how to develop a fixed-point, model-state-theoretic and proof theoretic semantics for such programs. The work of Melvin Fitting on developing a generalized semantics for multivalued logic programming is extended here to arbitrary abstract logics. We present examples to show how our semantics is robust enough to be applicable to various non-classical logics like temporal …
Strong Completeness Results For Paraconsistent Logic Programming, Howard A. Blair, V. S. Subrahmanian
Strong Completeness Results For Paraconsistent Logic Programming, Howard A. Blair, V. S. Subrahmanian
Electrical Engineering and Computer Science - Technical Reports
In [6], we introduced a means of allowing logic programs to contain negations in both the head and the body of a clause. Such programs were called generally Horn programs (GHPs, for short). The model-theoretic semantics of GHPs were defined in terms of four-valued Belnap lattices [5]. For a class of programs called well-behaved programs, an SLD-resolution like proof procedure was introduced. This procedure was proven (under certain restrictions) to be sound (for existential queries) and complete (for ground queries). In this paper, we remove the restriction that programs be well-behaved and extend our soundness and completeness results to apply …
Metaprolog Design And Implementation, Hamid Bacha
Metaprolog Design And Implementation, Hamid Bacha
Electrical Engineering and Computer Science - Technical Reports
Many researchers in the area of logic programming have recognized the limits of logic languages such as Prolog and suggested a meta level approach as an alternative. Some of the main drawbacks cited are the control strategy, the presence of a single database, and the ad hoc extensions to the base logic programming paradigm to allow the dynamic modification of the database. The MetaProlog language, which includes Prolog and some of its metalanguage, deals with some of these problems. In this paper, the design and implementation of MetaProlog are described and the changes to the Warren Abstract Machine (WAM) on …