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.
Functional programming languages, since their early days, have been regarded as the holy grail of parallelism. And, in fact, the absence of race conditions, coupled with algorithmic skeletons such as map and reduce, h...
详细信息
Functional programming languages, since their early days, have been regarded as the holy grail of parallelism. And, in fact, the absence of race conditions, coupled with algorithmic skeletons such as map and reduce, have given developers the opportunity to write many different techniques aimed at the automatic parallelization of programs. However, there are many functional programs that are still difficult to parallelize. This difficulty stems from many factors, including the complex syntax of recursive functions. This paper provides new equipment to deal with this problem. Such instrument consists of an insight, plus a code transformation that is enabled by this insight Concerning the first contribution, we demonstrate that many recursive functions can be rewritten as a combination of associative operations. We group such functions into two categories, which involve monoid and semiring operations. Each of these categories admits a parallel implementation. To demonstrate the effectiveness of this idea, we have implemented an automatic code rewriting tool for Haskell, and have used it to convert six well-known recursive functions to algorithms that run in parallel. Our tool is totally automatic, and it is able to deliver non-trivial speedups upon the sequential version of the programs that it receives. In particular, the automatically generated parallel code delivers good scalability when varying the number of threads or the input size. (C) 2018 Elsevier B.V. All rights reserved.
The intrinsic complexity of learning compares the difficulty of learning classes of objects by using some reducibility notion. For several types of learning recursive functions, both natural complete classes are exhib...
详细信息
The intrinsic complexity of learning compares the difficulty of learning classes of objects by using some reducibility notion. For several types of learning recursive functions, both natural complete classes are exhibited and necessary and sufficient conditions for completeness are derived. Informally, a class is complete iff both its topological structure is highly complex while its algorithmic structure is easy. Some self-describing classes turn out to be complete. Furthermore, the structure of the intrinsic complexity is shown to be much richer than the structure of the mind change complexity, though in general, intrinsic complexity and mind change complexity can behave "orthogonally". (C) 2003 Elsevier Science (USA). All rights reserved.
The generation of some classes of recursive functions by superpositions of simple arithmetic functions is discussed. A finite basis in the class FFOM under superposition is constructed. The constructions use simple ar...
详细信息
The generation of some classes of recursive functions by superpositions of simple arithmetic functions is discussed. A finite basis in the class FFOM under superposition is constructed. The constructions use simple arithmetic functions and function standard for the majority of programming languages. Finite bases can be constructed in the hierarchy classes under certain constraints on the superpositions. The class of functions elementary in the sense of Skolem is defined as the set of all functions obtained from the functions 0, x+1, and x-y by using the operations of superposition and restricted summation. The class FFOM is the set of all functions defined everywhere on the set bounded above by the functions.
We investigate homomorphic images of the semiring of recursive functions as models of the Π2fragment of Arithmetic, and some relations between this fragment, its models and recursion theory
We investigate homomorphic images of the semiring of recursive functions as models of the Π2fragment of Arithmetic, and some relations between this fragment, its models and recursion theory
Under consideration are the algebras of unary functions with supports in countable primitively recursively closed classes and composition operation. Each algebra of this type is proved to have continuum many maximal s...
详细信息
We prove that every sufficiently slow-growing diagonally non-recursive (DNR) function computes a real with effective Hausdorff dimension 1. We then show that, for any recursive unbounded and non-decreasing function j,...
详细信息
We prove that every sufficiently slow-growing diagonally non-recursive (DNR) function computes a real with effective Hausdorff dimension 1. We then show that, for any recursive unbounded and non-decreasing function j, there is a DNR function bounded by j that does not compute a Martin-Lof random real. Hence, there is a real of effective Hausdorff dimension 1 that does not compute a Martin- Lof random real. This answers a question of Reimann and Terwijn.
This work addresses the problem of verifying imperative programs that manipulate data structures, e.g., Rust programs. Data structures are usually modeled by Algebraic Data Types (ADTs) in verification conditions. Ind...
详细信息
This work addresses the problem of verifying imperative programs that manipulate data structures, e.g., Rust programs. Data structures are usually modeled by Algebraic Data Types (ADTs) in verification conditions. Inductive invariants of such programs often require recursively defined functions (RDFs) to represent abstractions of data structures. From the logic perspective, this reduces to solving Constrained Horn Clauses (CHCs) modulo both ADT and RDF. The underlying logic with RDFs is undecidable. Thus, even verifying a candidate inductive invariant is undecidable. Similarly, IC3-based algorithms for solving CHCs lose their progress guarantee: they may not find counterexamples when the program is unsafe. We propose a novel IC3-inspired algorithm Racer for solving CHCs modulo ADT and RDF (i.e., automatically synthesizing inductive invariants, as opposed to only verifying them as is done in deductive verification). Racer ensures progress despite the undecidability of the underlying theory, and is guaranteed to terminate with a counterexample for unsafe programs. It works with a general class of RDFs over ADTs called catamorphisms. The key idea is to represent catamorphisms as both CHCs, via relationification, and RDFs, using novel abstractions. Encoding catamorphisms as CHCs allows learning inductive properties of catamorphisms, as well as preserving unsatisfiabilty of the original CHCs despite the use of RDF abstractions, whereas encoding catamorphisms as RDFs allows unfolding the recursive definition, and relying on it in solutions. Abstractions ensure that the underlying theory remains decidable. We implement our approach in Z3 and show that it works well in practice.
暂无评论