Genetic Programming (GP) [1] often uses a tree form of a graph to represent solutions. An extension to this representation, Automatically Defined functions (ADFs) [1] is to allow the ability to express modules. In [2]...
详细信息
ISBN:
(纸本)3540331433
Genetic Programming (GP) [1] often uses a tree form of a graph to represent solutions. An extension to this representation, Automatically Defined functions (ADFs) [1] is to allow the ability to express modules. In [2] we proved that the complexity of a function is independent of the primitive set (function set and terminal set) if the representation has the ability to express modules. This is essentially due to the fact that if a representation can express modules, then it can effectively define its own primitives at a constant cost. This is reminiscent of the result that the complexity of a bit string is independent of the choice of Universal Turing Machine (UTM) (within an additive constant) [3], the constant depending on the UTM but not on the function. The representations typically used in GP are not capable of expressing recursion, however a few researchers have introduced recursion into their representations. These representations are then capable of expressing a wider classes of functions, for example the primitive recursive functions (PRFs). We prove that given two representations which express the PRFs (and only the PRFs), the complexity of a function with respect to either of these representations is invariant within an additive constant. This is in the same vein as the proof of the invariants of Kolmogorov complexity [3] and the proof in [2].
This paper concerns speculative parallelization as a method of improving computations efficiency and also as a method of reducing the problem solving time with reference to its sequential version. Speculative parallel...
详细信息
ISBN:
(纸本)9780769534725
This paper concerns speculative parallelization as a method of improving computations efficiency and also as a method of reducing the problem solving time with reference to its sequential version. Speculative parallelization is proposed or a particular class of problems, described as recursive functions taking values from finite sets. It refers to speculative execution of consecutive iteration steps, each of which, except the first one, depends on the preceding iteration step yet before it ends. Assuming that in the sequential version one iteration is performed in one linear execution time step (hereinafter referred to as computational step), then the aim of the speculative parallelization is the reduction of the total number of computational steps and thus execution of more than one iteration in one time step. The essence of the problem is that we assume some mapping schemes of arguments into the set of possible values of the function in speculative computing, i.e. there exists precise information about the possible values that the function can take for particular arguments. This paper presents simulation results for the chosen mapping schemes, illustrating how the number of steps, required to compute the value of the function for the given argument, depends on the structure of the mapping scheme and the number of used parallel threads.
This paper is devoted to the statement and proof of a theorem showing how recursive definitions whose associated call graphs satisfy certain shape conditions can be converted systematically into efficient bottom-up ta...
详细信息
ISBN:
(纸本)9783540705932
This paper is devoted to the statement and proof of a theorem showing how recursive definitions whose associated call graphs satisfy certain shape conditions can be converted systematically into efficient bottom-up tabulation schemes. The increase in efficiency can be dramatic, typically transforming an exponential time algorithm into one that takes only quadratic time. The proof of the theorem relies heavily on the theory of zips developed by Roland Backhouse and Paul Hoogendijk.
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...
详细信息
ISBN:
(纸本)3540662014
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).
Blum and Plum (1975) showed that a class B of suitable recursive approximations to the halting problem is reliably EX-learnable. These investigations are carried on by showing that B is neither in NUM nor robustly EX-...
详细信息
ISBN:
(纸本)3540667482
Blum and Plum (1975) showed that a class B of suitable recursive approximations to the halting problem is reliably EX-learnable. These investigations are carried on by showing that B is neither in NUM nor robustly EX-learnable. Since the definition of the class B is quite natural and does not contain any self-referential coding, B serves as an example that the notion of robustness for learning is quite more restrictive than intended. Moreover, variants of this problem obtained by approximating any given recursively enumerable set A instead of the halting problem B are studied. All corresponding function classes U(A) are still EX-inferable but may fail to be reliably EX-learnable, for example if A is non-high and hypersimple. Additionally, it is proved that ZA(A) is neither in NUM nor robustly EX-learnable provided A is part of a recursively inseparable pair, A is simple but not hypersimple or A is neither recursive nor high. These results provide more evidence that there is still some need to find an adequate notion for "naturally learnable function classes."
Nonconstructive proofs are a powerful mechanism in mathematics. Furthermore, nonconstructive computations by various types of machines and automata have been considered by e.g., Karp and Lipton [17] and Freivalds [11]...
详细信息
ISBN:
(纸本)9783642208775
Nonconstructive proofs are a powerful mechanism in mathematics. Furthermore, nonconstructive computations by various types of machines and automata have been considered by e.g., Karp and Lipton [17] and Freivalds [11]. They allow to regard more complicated algorithms from the viewpoint of much more primitive computational devices. The amount of nonconstructivity is a quantitative characterization of the distance between types of computational devices with respect to solving a specific problem. In the present paper, the amount of nonconstructivity in learning of recursive functions is studied. Different learning types are compared with respect to the amount of nonconstructivity needed to learn the whole class of general recursive functions. Upper and lower bounds for the amount of nonconstructivity needed are proved.
In this paper we present a novel termination order the predicative lexicographic path order (PLPO for short), a syntactic restriction of the lexicographic path order. As well as lexicographic path orders, several non-...
详细信息
ISBN:
(纸本)9783319124667;9783319124650
In this paper we present a novel termination order the predicative lexicographic path order (PLPO for short), a syntactic restriction of the lexicographic path order. As well as lexicographic path orders, several non-trivial primitive recursive equations, e.g., primitive recursion with parameter substitution, unnested multiple recursion, or simple nested recursion, can be oriented with PLPOs. It can be shown that the PLPO however only induces primitive recursive upper bounds on derivation lengths of compatible rewrite systems. This yields an alternative proof of a classical fact that the class of primitive recursive functions is closed under those non-trivial primitive recursive equations.
作者：
Gervais, FFrappier, MLaleau, RCEDRIC
CNAM-IIE France GRIL
Département d'Informatique Université de Sherbrooke Canada LACL
Université Paris 12 Département Informatique IUT Fontainebleau France
EB3 is a trace-based formal language created for the specification of information systems (IS). Attributes, linked to entities and associations of an IS, are computed in EB3 by recursive functions on the valid traces ...
详细信息
ISBN:
(纸本)0769524354
EB3 is a trace-based formal language created for the specification of information systems (IS). Attributes, linked to entities and associations of an IS, are computed in EB3 by recursive functions on the valid traces of the system. We aim at synthesizing relational database transactions that correspond to EB3 attribute definitions. Each EB3 action is translated into a transaction. EB3 attribute definitions are analysed to determine the key values affected by each action. Some key values are retrieved from SELECT statements that correspond to first-order predicates in EB3 attribute definitions. To avoid problems with the sequencing of SQL statements in the transactions, temporary variables and/or tables are introduced for these key values. Generation of DELETE statements is straightforward, but distinguishing updates from insertions of tuples requires more analysis.
In this paper, we investigate reflective inductive inference of recursive functions. A reflective IIM is a learning machine that is additionally able to assess its own competence., First, we formalize reflective learn...
详细信息
ISBN:
(纸本)3540001700
In this paper, we investigate reflective inductive inference of recursive functions. A reflective IIM is a learning machine that is additionally able to assess its own competence., First, we formalize reflective learning from arbitrary example sequences. Here, we arrive at four different types of. reflection: reflection in the limit, optimistic, pessimistic and exact, reflection. Then, for learning in the limit, for consistent learning types and for finite learning, we compare the learning power of reflective IIMs with each other as well as with the one of standard IIMs. Finally, we compare reflective learning from arbitrary input sequences with reflective learning from canonical input sequences. In this context, an open question regarding total-consistent identification could be solved: it holds T-CONSa subset of T-CONS.
暂无评论