We present a (relatively) short mechanized proof that Coq types any recursive function which is provably total in Coq. The well-founded (and terminating) induction scheme, which is the foundation of Coq recursion, is ...
详细信息
ISBN:
(纸本)9783319661070
We present a (relatively) short mechanized proof that Coq types any recursive function which is provably total in Coq. The well-founded (and terminating) induction scheme, which is the foundation of Coq recursion, is maximal. We implement an unbounded minimization scheme for decidable predicates. It can also be used to reify a whole category of undecidable predicates. This development is purely constructive and requires no axiom. Hence it can be integrated into any project that might assume additional axioms.
*** [Bar74] has proved that there are classes of total recursive functions which are EX-identifiable but their union is not. We prove that there are no 3 classes U1, U2, U3 such that U1∪U2,U1∪U3 and U2∪U3 would be ...
详细信息
We address the problem of proving the equivalence of two recursive functions that have different base-cases and/or are not in lockstep. None of the existing software equivalence checkers (like REVE, RVT, SYMDIFF), or ...
详细信息
ISBN:
(纸本)9783319489896;9783319489889
We address the problem of proving the equivalence of two recursive functions that have different base-cases and/or are not in lockstep. None of the existing software equivalence checkers (like REVE, RVT, SYMDIFF), or general unbounded software model-checkers (like SEAHORN, HSFC, AUTOMIZER) can prove such equivalences. We show a proof rule for the case of different base cases, based on separating the proof into two parts-inputs which result in the base case in at least one of the two compared functions, and all the rest. We also show how unbalanced unrolling of the functions can solve the case in which the functions are not in lock-step. In itself this type of unrolling may again introduce the problem of the different base cases, and we show a new proof rule for solving it. We implemented these rules in our regression-verification tool RVT. We conclude by comparing our approach to that of Felsig et al.'s counterexample-based refinement, which was implemented lately in their equivalence checker REVE.
This paper investigates closedness properties in relation with team learning of total recursive functions. One of the first problems solved for any new identification types is the following: "Does the identifiabi...
详细信息
Although the recent popularity of parallel-computing environments has called for parallel programs, it is difficult for nonspecialists to develop those that are efficient. What is required are parallelization methods ...
详细信息
ISBN:
(纸本)9783642122507
Although the recent popularity of parallel-computing environments has called for parallel programs, it is difficult for nonspecialists to develop those that are efficient. What is required are parallelization methods that can automatically generate efficient parallel programs from sequential ones. In this paper, we propose an automatic method of parallelization for recursive functions. The key is a quantifier-elimination-based derivation of all operator that shrinks function closures representing partial computations. Once we obtain such an operator, we can split the input structure and perform computation on each part in parallel. Our method has several features: it does not require any human help, it guarantees coniputational efficiency of generated programs, and it deals with complicated recursive functions such as those that are nonlinear recursive, non-self recursive, and accumulative.
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 (learning in the limit, learning with a ...
详细信息
ISBN:
(纸本)9781581131673
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 (learning in the limit, learning with a bounded number of mind changes, learning with anomalies), both generic complete classes are exhibited and necessary and sufficient conditions for completeness are derived. Informally, a class is complete if both its topological structure is highly complex while its algorithmic structure is surprisingly easy. Counter-intuitively, some self-describing classes turn out to be complete.
We introduce a powerful termination algorithm for structurally recursive functions that improves on the core ideas behind lexicographic termination algorithms for functional programs. The algorithm generates linear-le...
详细信息
A refinement of the structural complexity measure depth of nesting in loop programs leads to a new characterization of Cleave's ω2-hierarchy. This characterization allows to discover new properties (for instance ...
详细信息
Within the last years, the interest in efficient implementations of high level interpreter-based applicative languages has increased considerably, both in the areas of software engineering and artificial intelligence....
详细信息
The intrinsic complexity of a relation on a given computable structure is captured by the notion of its degree spectrum – the set of Turing degrees of images of the relation in all computable isomorphic copies of tha...
详细信息
暂无评论