The work presented in this paper demonstrates a new method for recursive queries in a complex object data base system. The method is called functional recursion. Most previous approaches express recursive queries by s...
详细信息
The work presented in this paper demonstrates a new method for recursive queries in a complex object data base system. The method is called functional recursion. Most previous approaches express recursive queries by set oriented recursion, i.e. they allow us to define a set M recursively by an equation M = f(M). In contrast to set oriented recursion, functional recursion as defined in this paper allows the user to define a function f recursively by an equation f = F(f). As opposed to recursive functions written in a conventional programming language, the termination criterion which sometimes is rather complex does not have to be programmed by the user but is given implicity. By providing appropriate parameters to a function, the user can integrate a selection into the recursion in a convenient and natural way. This is not the case for set oriented recursion. When using set recursion, the user is forced to formulate a query which computes more than really needed. It is the task of the optimizer then to push the subsequent selection into the recursion. This mean that the user cannot write the query in a natural way and the system then has to figure out what the user wanted. All these problems are avoided when using recursive functions as defined in this paper. Moreover, a solution based on key oriented duplicate elimination is presented which solves the problem of list and arithmetics in the context of recursive functions. The method is illustrated by bill-of-materials examples and by a railroad example.
A recursive function on a tree is a function in which each leaf has a given value, and each internal node has a value equal to a function of the number of children, the values of the children, and possibly an explicit...
详细信息
A recursive function on a tree is a function in which each leaf has a given value, and each internal node has a value equal to a function of the number of children, the values of the children, and possibly an explicitly specified random elementU. The value of the root is the key quantity of interest in general. In this study, all node values and function values are in a finite setS. In this note, we describe the limit behavior when the leaf values are drawn independently from a fixed distribution onS, and the treeT(n)is a random Galton-Watson tree of sizen.
In a series of articles, we developed a method to translate general recursive functions written in a functional programming style into constructive type theory. Three problems remained: the method could not properly d...
详细信息
ISBN:
(纸本)3540255931
In a series of articles, we developed a method to translate general recursive functions written in a functional programming style into constructive type theory. Three problems remained: the method could not properly deal with functions taking functional arguments, the translation of terms containing A-abstractions was too strict, and partial application of general recursive functions was not allowed. Here, we show how the three problems can be solved by defining a type of partial functions between given types. Every function, including arguments to higher order functions, A-abstractions and partially applied functions, is then translated as a pair consisting of a domain predicate and a function dependent on the predicate. Higher order functions are assigned domain predicates that inherit termination conditions from their functional arguments. The translation of a A-abstraction does not need to be total anymore, but generates a local termination condition. The domain predicate of a partially applied function is defined by fixing the given arguments in the domain of the original function. As in our previous articles, simultaneous induction-recursion is required to deal with nested recursive functions. Since by using our method the inductive definition of the domain predicate can refer globally to the domain predicate itself, here we need to work on an impredicative type theory for the method to apply to all functions. However, in most practical cases the method can be adapted to work on a predicative type theory with type universes.
The primary aim of this work is to provide new tools for machine learning and reasoning within a framework of computing with holistic data representations. Specifically, we demonstrate recursive construction of mappin...
详细信息
ISBN:
(纸本)9781509006199
The primary aim of this work is to provide new tools for machine learning and reasoning within a framework of computing with holistic data representations. Specifically, we demonstrate recursive construction of mappings and functions in high-dimensional computing with random vectors - a connectionist computing model which provides benefits similar to neural networks, but allows compositional learning. The computational operations considered in this work are applicable in learning by generalizing from small sets of example data. We demonstrate their use by constructing a simple reasoning model which learns modulo 10 addition and subtraction from a minimal set of examples. Finally, we give examples on how the presented computational operations can be used to compose and manipulate more complex structures in computing with high-dimensional random vectors.
The usual definition facilities in theorem provers cannot handle all recursive functions on lazy lists;the filter function is a prime counterexample. We present two new ways of directly defining functions like filter ...
详细信息
We prove that string rewriting systems which reduce by Higman's lemma exhaust the multiply recursive functions. This result provides a full characterisation of the expressiveness of Higman's lemma when applied...
详细信息
We prove that string rewriting systems which reduce by Higman's lemma exhaust the multiply recursive functions. This result provides a full characterisation of the expressiveness of Higman's lemma when applied to rewriting theory. The underlying argument of our construction is to connect the order type and the derivation length via the Hardy hierarchy. (C) 2002 Elsevier Science (USA).
Studying the learnability of classes of recursive functions has attracted considerable interest for at least four decades. Starting with Gold's (1967) model of learning in the limit, many variations, modifications...
详细信息
Studying the learnability of classes of recursive functions has attracted considerable interest for at least four decades. Starting with Gold's (1967) model of learning in the limit, many variations, modifications and extensions have been proposed. These models differ in some of the following: the mode of convergence, the requirements intermediate hypotheses have to fulfill, the set of allowed learning strategies, the source of information available to the learner during the learning process, the set of admissible hypothesis spaces, and the learning goals. A considerable amount of work done in this field has been devoted to the characterization of function classes that can be learned in a given model, the influence of natural, intuitive postulates on the resulting learning power, the incorporation of randomness into the learning process, the complexity of learning, among others. On the occasion of Rolf Wiehagen's 60th birthday, the last four decades of research in that area are surveyed, with a special focus on Rolf Wiehagen's work, which has made him one of the most influential scientists in the theory of learning recursive functions. (C) 2008 Elsevier B.V. All rights reserved.
In this paper we present Ariadne, a compiler that extracts parallelism from recursive function calls. Ariadne takes as input C code enhanced with directives for recursive functions and automatically produces code for ...
详细信息
In this paper we present Ariadne, a compiler that extracts parallelism from recursive function calls. Ariadne takes as input C code enhanced with directives for recursive functions and automatically produces code for multi-core architectures. It produces code for the POSIX standard, the OpenMP model and the Cilk programming language, which run on a wide variety of computing systems. Ariadne also produces code for SL, a programming language proposed for the SVP processor and model. This is of special interest, since we can map certain function calls onto SVP, which contain inherent parallelism that cannot efficiently be expressed in other programming models. Ariadne is the only compiler that extracts parallelism from various forms of recursive functions using directives. It is also the only compiler that handles all forms of reduction operations for addition, subtraction, multiplication and division. The experimental results are very promising showing significant speedups in all benchmarks. (C) 2015 Elsevier Inc. All rights reserved.
暂无评论