21.
A Safe Calculus and Algebra for Querying Functional Logic Deductive Databases ⋆
- Jesús M. Almendros-jiménez; Antonio Becerra-terón
Abstract. In this paper, we present an extended relational calculus and algebra for a functional logic deductive database language. The extended relational calculus is based on the relational first-order logic, by adding constraints in the form of equalities and disequalities over complex (partially defined and possibly infinite) values and interpreted functions. In addition, we propose the notion of safety over calculus formulas in order to guarantee the property of domain independence. In the case of the extended relational algebra, we provide a generalization of the selection and projection operators in order to restructure complex values by means of constructors and...
22.
A Safe Calculus and Algebra for Querying Functional Logic Deductive Databases
- Jesús M. Almendros-Jiménez; Antonio Becerra-Terón
In this paper, we present an extended relational calculus and algebra for a functional logic deductive database language. The extended relational calculus is based on the relational rst-order logic, by adding constraints in the form of equalities and disequalities over complex (partially de ned and possibly in nite) values and interpreted functions. In addition, we propose the notion of safety over calculus formulas in order to guarantee the property of domain independence. In the case of the extended relational algebra, we provide a generalization of the selection and projection operators in order to restructure complex values by means of constructors...
23.
Towards An Object-Oriented Methodology for Deductive Synthesis of Logic Programs
- Kung-kiu Lau,Fachgebiet Intellektik,Fachbereich Informatik,Technische Hochschule Darmstadt
. Quality software must be reusable, extensible, and reliable.
Object-oriented programming purports to achieve these attributes by
the use of classes and inheritance (informally). In this paper, we show
how our existing approach to deductive synthesis of logic programs can
serve as the basis for an object-oriented methodology for formal program
development that achieves reusability, extensibility and correctness
(formally).
1 Introduction
Object-oriented programming is very much seen as the standard bearer of the
software industry nowadays, because it purports to achieve the key attributes of
any quality software: reusability , extensibility , and reliability (see e.g. [12, 13]).
Object-oriented programming achieves reusability and extensibility by using a
class as the basic modular...
24.
Towards An Object-Oriented Methodology for Deductive Synthesis of Logic Programs
- Kung-kiu Lau,Fachgebiet Intellektik,Fachbereich Informatik,Technische Hochschule Darmstadt
. Quality software must be reusable, extensible, and reliable.
Object-oriented programming purports to achieve these attributes by
the use of classes and inheritance (informally). In this paper, we show
how our existing approach to deductive synthesis of logic programs can
serve as the basis for an object-oriented methodology for formal program
development that achieves reusability, extensibility and correctness
(formally).
1 Introduction
Object-oriented programming is very much seen as the standard bearer of the
software industry nowadays, because it purports to achieve the key attributes of
any quality software: reusability , extensibility , and reliability (see e.g. [12, 13]).
Object-oriented programming achieves reusability and extensibility by using a
class as the basic modular...
25.
A Computational Model for Functional Logic Deductive Databases, available in http://www.ual.es/~jalmen
- Jesús M. Almendros-jiménez; Antonio Becerra-terón; Jaime Sánchez-hernández
Abstract. This paper adds the handling of negative information to a functional-logic deductive database language. By adopting as semantics for negation the so-called CRWLF, wherein the negation is intended as ’finite failure ’ of reduction, we will define Herbrand algebras and models for this semantics and a fix point operator to be used in a new goaldirected bottom-up evaluation mechanism based on magic transformations. This bottom-up evaluation will simulate the top-down one of the original program; in fact, it will carry out a goal-directed lazy evaluation. 1
26.
A Linear Logic Semantics for Object-Oriented, Deductive and Active Databases
Girard's linear logic [18] provides powerful means for studying state transformations
and resource consumption in computations within a completely logical framework.
The starting point of this work is Forum [22, 23], a presentation of higher order
linear logic which is an abstract logic programming language[24], i.e., complete with
respect to uniform proofs (cut-free and goal-directed proofs). A subset of Forum's
formulas which form the logic programming language E hhf [11, 13], have been isolated
and proved to be well-suited to encode a notion of state into sequents and proofs, to
model state updates, and to provide constructs for parallel execution.
In this paper, we will show how it...
27.
Negation in Logic and Deductive Databases
- Xuegang Wang
This thesis studies negation in logic and deductive databases. Among other things, two kinds of negation are discussed in detail: strong negation and nonmonotonic negation. In the logic part, we have constructed a first-order logic CF 0 of strong negation with bounded quantifiers. The logic is based on constructive logics, in particular, Thomason's logic CF. However, unlike constructive logic, quantifiers in our system as in Thomason's are static rather than dynamic. For the logic CF 0 , the usual Kripke formal semantics is defined but based on situations instead of conventional possible worlds. A sound and complete axiomatic system of...
28.
NAIL (Not Another Implementation of Logic) was a prototype deductive database system developed at Stanford.
- Were Marcia Derr,Shinichi Morishita
F14.69> end;
ffl Condition is a rule body.
ffl Its value is "true" iff the body is nonempty.
ffl Similar idea: repeat, loop, if-then-else statements.
Example:
(1) module semi;
(2) export main(:);
(3) edb arc(X,Y), path(X,Y);
(4) prog main(:)
(5) rels newPath(X,Y);
(6) arc(X,Y) := --.
(7) arc(1,2).
(8) arc(2,3).
(9) arc(3,4).
(10) arc(4,5).
(11) arc(2,4).
(12) newPath(X,Y) := arc(X,Y).
(13) path(X,Y) := --.
(14) while newPath(X,Y) do
(15) path(X,Y) += newPath(X,Y).
(16) newPath(X,Y) := newPath(X,Z) & arc(Z,Y).
(17) newPath(X,Y) -= path(X,Y).
(18) end;
(19) end
(20) end
This program performs seminaive
29.
On Specification Frameworks and Deductive Synthesis of Logic Programs
- Kung-kiu Lau
this paper, we
take a closer look at such frameworks. We shall explain what they are, and how
they can be used to specify properties such as correctness and modularity (and
hence reusability).
Moreover, we shall show that there is a close two-way relationship between
specification frameworks and deductive synthesis. In particular, a deductive synthesis
process can provide a useful feedback mechanism which can not only check
for desirable properties in the specification framework, but also improve the
framework (with regard to such properties) using the result of the synthesis.
In our approach to modularity, we borrow many of the basic ideas developed
in the algebraic approach (e.g. [6, 7,...
30.
On Specification Frameworks and Deductive Synthesis of Logic Programs
- Kung-kiu Lau
this paper, we
take a closer look at such frameworks. We shall explain what they are, and how
they can be used to specify properties such as correctness and modularity (and
hence reusability).
Moreover, we shall show that there is a close two-way relationship between
specification frameworks and deductive synthesis. In particular, a deductive synthesis
process can provide a useful feedback mechanism which can not only check
for desirable properties in the specification framework, but also improve the
framework (with regard to such properties) using the result of the synthesis.
In our approach to modularity, we borrow many of the basic ideas developed
in the algebraic approach (e.g. [6, 7,...
31.
A Dynamic Logic for Deductive Verification of Concurrent Programs
In this paper, we present an approach aiming at full functional deductive verification of concurrent Java programs, based on symbolic execution. We define a Dynamic Logic and a deductive verification calculus for a restricted fragment of Java with native concurrency primitives. Even though we cannot yet deal with non-atomic loops, employing the technique of symmetry reduction allows us to verify unbounded systems. The calculus has been implemented within the KeY system, and we demonstrate it by verifying a central method of the StringBuffer class from the Java standard library.
32.
The Halting Problem for Deductive Synthesis of Logic Programs
- Kung-kiu Lau,Mario Ornaghi,Sten- Ake Tarnlund
Deductive synthesis methods derive programs in an incremental manner, and therefore
pose a halting problem -- when can synthesis stop with a correct program? We
give a characterisation of this problem and state a halting principle as a solution.
Another characteristic of deductive synthesis is that it may derive several correct
programs, giving rise to another question -- which correct programs are desirable?
We show that the answer is related to the halting problem, via the notion of steadfast,
or reusable, programs as desirable programs. Our work also reveals that Clark's
idea of the completion of a program is central to deductive synthesis, since it is the
basis...
33.
Logic: deductive and inductive.
- Bain, Alexander, 1818-1903.
New and rev. ed.
34.
INTRODUCCION A LA LOGICA DEDUCTIVA Y TEORIA DE LOS CONJUNTOS
- Salazar Resines, Javier
35.
Introducción a la lógica deductiva y teoría de los conjuntos
- Salazar Resines, Javier
36.
Introducción a la Lógica Deductiva y Teoría de los Conjuntos
- Salazar Resines, Javier
968-58-0213-0
37.
A Compositional Semantics for Logic Programs and Deductive Databases
- Franccois Bry
Considering integrity constraints and program composition, it is first argued that a semantics for logic programs and deductive databases should not accommodate inconsistencies globally like in classical logic, but locally. It is then shown that minimal logic, a natural deduction style weakening of classical logic, is sufficient to provide for a proof theory for a generalization of logic programs corresponding to deductive databases with integrity constraints and disjunctive logic programs. Minimal logic differs from classical logic inasmuch as it precludes refutation proofs. Finally, a (nonclassical) model theory is proposed for generalized programs, which is based on a weakening of the...
38.
Minimal founded semantics for disjunctive logic programs and deductive
databases
- Furfaro, Filippo; Greco, Gianluigi; Greco, Sergio
In this paper, we propose a variant of stable model semantics for disjunctive
logic programming and deductive databases. The semantics, called minimal
founded, generalizes stable model semantics for normal (i.e. non disjunctive)
programs but differs from disjunctive stable model semantics (the extension of
stable model semantics for disjunctive programs). Compared with disjunctive
stable model semantics, minimal founded semantics seems to be more intuitive,
it gives meaning to programs which are meaningless under stable model semantics
and is no harder to compute. More specifically, minimal founded semantics
differs from stable model semantics only for disjunctive programs having
constraint rules or rules working as constraints. We study the expressive power
of the...
39.
A Compositional Semantics for Logic Programs and Deductive Databases
- François Bry
Considering integrity constraints and program composition, it is argued that a semantics for logic programs and deductive databases should not accommodate inconsistencies globally like in classical logic, but locally. It is shown that minimal logic, a weakening of classical logic which precludes refutation proofs, is sufficient to provide for a proof theory for generalized programs corresponding to deductive databases and disjunctive logic programs. A (nonclassical) model theory is proposed for these programs, which allows local inconsistencies. The proposed semantics naturally extends the minimal model and completion semantics of positive programs and is compositional. Arguably, it appropriately conveys a practician's intuition....
40.
A Relational Algebra for Functional Logic Deductive Databases?
Abstract. In this paper, we study the integration of functional logic programming and databases by presenting a data model, and a query and data definition language. The data model is adopted from functional logic programming by allowing complex values. The query and data definition language is based on the use of algebra expressions built from a set of algebra operators over an extended relational algebra. In addition, algebra expressions can be used for defining functions, typical in a functional logic program. 1 Introduction Database technology is involved in most software applications. For this reason, functional logic languages [9] should include...
