Path coverage is of critical importance in software testing and verification, and further, path explosion is a well-known challenge for automatic software analysis techniques like symbolic execution [7]. Asymptotic Pa...
详细信息
ISBN:
(纸本)9798350322637
Path coverage is of critical importance in software testing and verification, and further, path explosion is a well-known challenge for automatic software analysis techniques like symbolic execution [7]. Asymptotic Path Complexity (APC), a code complexity metric developed in my research lab, formalizes the quantitative measurement of path explosion.
The present paper surveys some results from the inductive inference of recursive functions, which are related to the characterization of inferrible function classes in terms of complexity theory, and in terms of recur...
详细信息
ISBN:
(数字)9783030514662
ISBN:
(纸本)9783030514662;9783030514655
The present paper surveys some results from the inductive inference of recursive functions, which are related to the characterization of inferrible function classes in terms of complexity theory, and in terms of recursive numberings. Some new results and open problems are also included.
Our goal is to define a type of partial recursive functions in constructive type theory. In a series of previous articles, we studied two different formulations of partial functions and general recursion. We could obt...
详细信息
ISBN:
(纸本)9783540710653
Our goal is to define a type of partial recursive functions in constructive type theory. In a series of previous articles, we studied two different formulations of partial functions and general recursion. We could obtain a type only by extending the theory with either an impredicative universe or with coinductive definitions. Here we present a new type constructor that eludes such entities of dubious constructive credentials. We start by showing how to break down a recursive function definition into three components: the first component generates the arguments of the recursive calls, the second evaluates them, and the last computes the output from the results of the recursive calls. We use this dissection as the basis for the introduction rule of the new type constructor. Every partial recursive function is associated with an inductive domain predicate;evaluation of the function requires a proof that the input values satisfy the predicate. We give a constructive justification for the new construct by interpreting it into the base type theory. This shows that the extended theory is consistent and constructive.
Recently, functions over the reals that extend elementarily computable functions over the integers have been proved to correspond to the smallest class of real functions containing some basic functions and closed by c...
详细信息
ISBN:
(纸本)3540252614
Recently, functions over the reals that extend elementarily computable functions over the integers have been proved to correspond to the smallest class of real functions containing some basic functions and closed by composition and linear integration. We extend this result to all computable functions: functions over the reals that extend total recursive functions over the integers are proved to correspond to the smallest class of real functions containing some basic functions and closed by composition, linear integration and a very natural unique minimization schema.
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.
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 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.
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.
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."
暂无评论