An important property of strategies used to solve goals in functionallogicprogramming (FLP) languages is the complete exploration of the solution space. Integrating constraints into FLP proved to be useful in many c...
详细信息
ISBN:
(纸本)3540243623
An important property of strategies used to solve goals in functionallogicprogramming (FLP) languages is the complete exploration of the solution space. Integrating constraints into FLP proved to be useful in many cases, as the resulting constraint functionallogicprogramming (CFLP) offers more facilities and more efficient operational semantics. CFLP can be achieved by means of conditional rewrite systems with a narrowing-based operational semantics. A common idea to improve the efficiency of such operational semantics is to use specific algorithms from operations research as constraint solvers. If the algorithm does not return a complete set of solutions, the property of completeness might be lost. We present a real world timetabling problem illustrating this approach. We propose an algorithm, obtained as an integration of three known optimization algorithms for the linear assignment problem (LAP), enumerating solutions to the LAP in order of increasing weight, such that resolution of goals is complete again. We show, how the narrowing process can be tailored to use this algorithm and provide an efficient way to solve the timetable generation problem.
Constructor-Based Conditional Rewriting logic is a general framework for integrating first-order functional and logicprogramming which gives an algebraic semantics for non-deterministic functional-logic programs. In ...
详细信息
Constructor-Based Conditional Rewriting logic is a general framework for integrating first-order functional and logicprogramming which gives an algebraic semantics for non-deterministic functional-logic programs. In the context of this formalism, we introduce a simple notion of program module as an open program which can be extended together with several mechanisms to combine them. These mechanisms are based on a reduced set of operations. However, the high expressiveness of these operations enable us to model typical constructs for program modularization like hiding, export/import, genericity/instantiation, and inheritance in a simple way. We also deal with the semantic aspects of the proposal by introducing an immediate consequence operator, and studying several alternative semantics for a program module, based on this operator, in the line of logicprogramming: the operator itself, its least fixpoint (the least model of the module), the set of its pre-fixpoints (term models of the module), and some other variations in order to find a compositional and fully abstract semantics w.r.t. the set of operations and a natural notion of observability.
In this paper, we present an extended relational calculus for expressing queries in functional-logic deductive databases. This calculus is based on first-order logic and handles relation predicates, equalities and ine...
详细信息
In this paper, we present an extended relational calculus for expressing queries in functional-logic deductive databases. This calculus is based on first-order logic and handles relation predicates, equalities and inequalities over partially defined terms, and approximation equations. For the calculus formulas, we have studied syntactic conditions in order to ensure the domain independence property. Finally, we have studied its equivalence w.r.t. the original query language, which is based on equality and inequality constraints.
We present outside-in conditional narrowing for orthogonal conditional term rewriting systems, and show the completeness of leftmost-outside-in conditional narrowing with respect to normalizable solutions. We consider...
详细信息
We present outside-in conditional narrowing for orthogonal conditional term rewriting systems, and show the completeness of leftmost-outside-in conditional narrowing with respect to normalizable solutions. We consider orthogonal conditional term rewriting systems whose conditions consist of strict equality only. Completeness results are obtained for systems both with and without extra variables. The result bears practical significance since orthogonal conditional term rewriting systems can be viewed as a computation model for functional-logic programming languages and leftmost-outside-in conditional narrowing is the computing mechanism for the model.
暂无评论