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.
A theorem is presented which has applications in the numerical computation of fixed points of recursive functions. If a sequence of functions {fn} is convergent on a metric space I subset of R, then it is possible to ...
详细信息
A theorem is presented which has applications in the numerical computation of fixed points of recursive functions. If a sequence of functions {fn} is convergent on a metric space I subset of R, then it is possible to observe this behaviour on the set D subset of Q of all numbers represented in a computer. However, as D is not complete, the representation of fn on D is subject to an error. Then f(n) and f(m) are considered equal when its differences computed on D are equal or lower than the sum of error of each f(n) and f(m). An example is given to illustrate the use of the theorem.
The paper investigates whether it is possible to learn every enumerable classes of recursive functions from "typical" examples. "Typical" means, there is a computable family of finite sets, such th...
详细信息
ISBN:
(纸本)3540667482
The paper investigates whether it is possible to learn every enumerable classes of recursive functions from "typical" examples. "Typical" means, there is a computable family of finite sets, such that for each function in the class there is one set of examples that can be used in any suitable hypothesis space for this class of functions. As it will turn out, there are enumerable classes of recursive functions that are not learnable from "typical" examples. The learnable classes are characterized. The results are proved within an abstract model of learning from examples, introduced by Freivalds, Kinber and Wiehagen. Finally, the results are interpreted and possible connections of this theoretical work to the situation in real life classrooms are pointed out.
Virus Machines are a computational paradigm inspired by the manner in which viruses replicate and transmit from one host cell to another. This paradigm provides non-deterministic sequential devices. Non-restricted Vir...
详细信息
ISBN:
(纸本)9783319284750;9783319284743
Virus Machines are a computational paradigm inspired by the manner in which viruses replicate and transmit from one host cell to another. This paradigm provides non-deterministic sequential devices. Non-restricted Virus Machines are unbounded Virus Machines, in the sense that no restriction on the number of hosts, the number of instructions and the number of viruses contained in any host along any computation is placed on them. The computational completeness of these machines has been obtained by simulating register machines. In this paper, Virus Machines as function computing devices are considered. Then, the universality of non-restricted virus machines is proved by showing that they can compute all partial recursive functions.
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.
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.
In this paper, we report some empirical studies of students evaluating recursive functions defined according to the rules of the functional programming language Miranda, and describe the misconceptions and processing ...
详细信息
In this paper, we report some empirical studies of students evaluating recursive functions defined according to the rules of the functional programming language Miranda, and describe the misconceptions and processing strategies observed. We then discuss the implications of these observations as regards teaching content.
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).
暂无评论