Our aim is to define a new fixpoint semantics which correctly models finite failure. In order to achieve this goal a new fixpoint operator is derived from a "suitable" concrete semaoitics by defining a Galoi...
详细信息
ISBN:
(纸本)3540664920
Our aim is to define a new fixpoint semantics which correctly models finite failure. In order to achieve this goal a new fixpoint operator is derived from a "suitable" concrete semaoitics by defining a Galois insertion modeling finite failure. the corresponding abstract fixpoint semantics correctly models finite failure and is and-compositional.
TLA (the Temporal logic of Actions) is a linear temporal logic for specifying and reasoning about reactive systems. We define a subset of TLA whose formulas are amenable to validation by animation, withthe intent to ...
详细信息
ISBN:
(纸本)3540664920
TLA (the Temporal logic of Actions) is a linear temporal logic for specifying and reasoning about reactive systems. We define a subset of TLA whose formulas are amenable to validation by animation, withthe intent to facilitate the communication between domain and solution experts in the design of reactive systems.
Linear logic [4] has radsed a lot of interest in computer research, especially because of its resource sensitive nature. One hne of research studies proof construction procedures and their interpretation as computatio...
详细信息
ISBN:
(纸本)3540664920
Linear logic [4] has radsed a lot of interest in computer research, especially because of its resource sensitive nature. One hne of research studies proof construction procedures and their interpretation as computationil models, in the "logicprogramming" tradition. An efficient proof search procedure, based on a proof normalization result called "Focusing", has been described in [2]. Pocusing is described in terms of the sequent system of commutative Linear logic, which it refines in two steps. It is shown here that Pocusing Ccin also be interpreted in the proof-net formalism, where it appecirs, at least in the multiplicative fragment, to be a simple refinement of the "Splitting lemma" for proof-nets. this change of perspective allows to generalize the Focusing result to (the multiplicative fragment of) any logic where the "Splitting lemma" holds. this is, in particular, the CEise of the Non-Commutative logic of [1], and all the computational exploitation of Pocusing which has been performed in the commutative case can thus be revised and adapted to the non commutative case.
In this work, we develop a partial evaluation technique for residuating functional logic programs, which generalize the concurrent computation models for logic programs with delays to functional logic prograjns. We sh...
详细信息
ISBN:
(纸本)3540664920
In this work, we develop a partial evaluation technique for residuating functional logic programs, which generalize the concurrent computation models for logic programs with delays to functional logic prograjns. We show how to lift the nondeterministic choices from run time to specialization time. We ascertain the conditions under which the original and the trainsformed prograjn have the same answer expressions for the considered class of queries as well as the same floundering behavior. All these results are relevjint for prograim optimization in Curry, a functional logic language which is intended to become a staindard in this area. Preliminary empiriccil evaluation of the specialized Curry programs demonstrates that our technique also works well in practice and leads to substantial performance improvements. To our knowledge, this work is the first attempt to formally define and prove correct a generaJ scheme for the partisd evaluation of functional logic programs with delays.
Linear logic provides a logical framework to express ftindamentEd computationcil concepts in a declcirative style. As a consequence, it has been used as a sound foundation for the design of expressive progreimming and...
详细信息
ISBN:
(纸本)3540664920
Linear logic provides a logical framework to express ftindamentEd computationcil concepts in a declcirative style. As a consequence, it has been used as a sound foundation for the design of expressive progreimming and specification languages. Unfortunately, linearity is as convenient for specifying as difficult to implement. In particular, the successful implementation of linear logic Ismguages Eind provers involving context splitting strongly depends on the efficiency of the method computing a suitable split. A number of solutions have been proposed, referred to as lazy splitting or resource management systems. In this paper, we present a new resource management system for the Lolli linear logic Icinguage. We show that the choice of the structure employed to represent the contexts has a strong influence on the overall performcince of the resource mzinagement system. We also estimate the performsmce of previous proposals, and compare them to our new system.
Proving failure of queries for definite logic progrfims can be done by constructing a finite model of the program in which the query is false. A general purpose model generator for first order logic can be used for th...
详细信息
ISBN:
(纸本)3540664920
Proving failure of queries for definite logic progrfims can be done by constructing a finite model of the program in which the query is false. A general purpose model generator for first order logic can be used for this. A recent paper presented at PLILP98 shows how the peculiarities of definite progrcims can be exploited to obtain a better solution. there a procedure is described which combines abduction with tabulation and uses a meta-interpreter for heuristic control of the search. the current paper shows how similcir results Ccin be obtained by direct execution under the standard tabulation of the XSB-Prolog system. the loss of control is compensated for by better intelligent beicktracking cind more accurate failure analysis.
A heuristic method (computation of weighted averages) is considered for risk analysis. It is improved upon by utilizing the Perceptron Learning theorem and Quadratic programming. Experimental work shows that both tech...
详细信息
Datalog is a well-known database query language based on the logicprogramming paradigm. A general datalog program consists of a number of rules and facts. Programs containing a unique rule and possibly some facts are...
详细信息
ISBN:
(纸本)3540664920
Datalog is a well-known database query language based on the logicprogramming paradigm. A general datalog program consists of a number of rules and facts. Programs containing a unique rule and possibly some facts are called single rule programs (sirups). We study boththe combined and the program complexity of sirups, ie., the complexity of evaluating sirups over variable and fixed databases, respectively. Moreover, we study the descriptive complexity of sirups, i.e., their expressive power. In ail cases it turns out that even very restricted classes of sirups have the same complexity and essentially the same expressive power as general datalog programs. We show that the evaluation of single clause programs is EXPTIME complete (combined complexity), and, if restricted to linear recursive rules, PSPACE complete. Moreover, sirups with one recursive rule and one additional fact capture PTIME on ordered structures, if a certain data representation is assumed and certain predefined relations are provided. Our results are obtained by a uniform product construction which maps a datalog program into a single rule by essentially maintaining its semantics. We also prove that the datalog clause implication problem, i.e., deciding whether a datalog clause implies another one, is EXPTIME complete.
CHAT offers an Eilternative to SLG-WAM for implementing the suspension eind resumption of consumers that tabling needs;unlike SLG-WAM, it does not use freeze registers nor a complicated trail to preserve their executi...
详细信息
ISBN:
(纸本)3540664920
CHAT offers an Eilternative to SLG-WAM for implementing the suspension eind resumption of consumers that tabling needs;unlike SLG-WAM, it does not use freeze registers nor a complicated trail to preserve their execution environments. CHAT Eilso limits the amount of copying of CAT, which was previously put forwMd as another alternative to SLG-WAM. Although experimented results show that in preictice CHAT is competitive with - if not better than - SLG-WAM, there remains the annoying fact that on contrived programs the original CHAT can be made axbitraxily worse than SLG-WAM, i.e. the origincd CHAT has an intrinsically higher complexity. In this paper we show how to overcome this problem, in particular, we deal withthe two sources of higher complexity of CHAT: the repeated traversal of the choice point stack, Eind the lack of sufficient sharing of the trail. this is eichieved without fundamentally changing the underlying principle of CHAT by a technique that manipulates a Prolog choice point so that it assumes temporarily a different functionality smd in a way that is treinsparent to the underlying WAM. there is more potential use of this technique besides lowering the worst case complexity of CHAT: it leads to considering scheduling strategies that were not feasible before either in CHAT or in SLG-WAM. We aJso discuss extensively issues related to the implementation of the trail in a tabled logicprogramming system.
In this work, the notion of provability for first order linear temporal logic over finite time structures, FO-LTLfin, is studied. We show that the validity problem for such a logic is not recursively enumerable, hence...
详细信息
ISBN:
(纸本)3540664920
In this work, the notion of provability for first order linear temporal logic over finite time structures, FO-LTLfin, is studied. We show that the validity problem for such a logic is not recursively enumerable, hence FO-LTLfin is not recursively axiomatizable. this negative result however does not hold in the case of bounded validity, that is truth in all temporal models where the object domain is possibly infinite, but the underlying sequence of time points does not exceed a given size. A formula is defined to be A-valid if it is true in all tempered models whose underlying time frtime is not greater them κ, where κ is any fixed positive integer. In this work a tableau calculus is defined, that is sound and complete with respect to κ-validity, when given as input the initial formula and the bound κ on the size of the temporal models. the main feature of the system, extending the prepositional calculus defined in [7], is that of explicitly denoting time points and having tableau nodes labelled by either expressions intuitively stating that a formula holds in a given temporal interval or "temporal constraints" i.e. linear inequalities on time points. Branch closure is reduced to unsatisfiability over the integers of the set of temporal constraints in the branch.
暂无评论