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.
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).
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 ...
详细信息
暂无评论