The Experts below are selected from a list of 4185 Experts worldwide ranked by ideXlab platform
Luca Roversi - One of the best experts on this subject based on the ideXlab platform.
-
A class of Recursive Permutations which is Primitive Recursive complete
Theoretical Computer Science, 2020Co-Authors: Luca Paolini, Mauro Piccolo, Luca RoversiAbstract:Abstract We focus on total functions in the theory of reversible computational models. We define a class of Recursive permutations, dubbed Reversible Primitive Permutations ( RPP ) which are computable invertible total endo-functions on integers, so a subset of total reversible computations. RPP is generated from five basic functions (identity, sign-change, successor, predecessor, swap), two notions of composition (sequential and parallel), one functional iteration and one functional selection. RPP is closed by inversion and it is expressive enough to encode Cantor pairing and the whole class of Primitive Recursive Functions.
-
On a Class of Reversible Primitive Recursive Functions and Its Turing-Complete Extensions
New Generation Computing, 2018Co-Authors: Luca Paolini, Mauro Piccolo, Luca RoversiAbstract:Reversible computing is both forward and backward deterministic. This means that a uniquely determined step exists from the previous computational configuration (backward determinism) to the next one (forward determinism) and vice versa. We present the reversible Primitive Recursive functions (RPRF), a class of reversible (endo-)functions over natural numbers which allows to capture interesting extensional aspects of reversible computation in a formalism quite close to that of classical Primitive Recursive functions. The class RPRF can express bijections over integers (not only natural numbers), is expressive enough to admit an embedding of the Primitive Recursive functions and, of course, its evaluation is effective. We also extend RPRF to obtain a new class of functions which are effective and Turing complete, and represent all Kleene’s \(\upmu \)-Recursive functions. Finally, we consider reversible recursion schemes that lead outside the reversible endo-functions.
-
A Class of Reversible Primitive Recursive Functions
Electronic Notes in Theoretical Computer Science, 2016Co-Authors: Luca Paolini, Mauro Piccolo, Luca RoversiAbstract:Reversible computing is bi-deterministic which means that its execution is both forward and backward deterministic, i.e. next/previous computational step is uniquely determined. Various approaches exist to catch its extensional or intensional aspects and properties. We present a class RPRF of reversible functions which holds at bay intensional aspects and emphasizes the extensional side of the reversible computation by following the style of Dedekind-Robinson Primitive Recursive Functions. The class RPRF is closed by inversion, can only express bijections on integers - not only natural numbers -, and it is expressive enough to simulate Primitive Recursive Functions, of course, in an effective way.
Burkhart Wolff - One of the best experts on this subject based on the ideXlab platform.
-
FATES - Symbolic test case generation for Primitive Recursive functions
Formal Approaches to Software Testing, 2005Co-Authors: Achim D Brucker, Burkhart WolffAbstract:We present a method for the automatic generation of test cases for HOL formulae containing Primitive Recursive predicates. These test cases can be used for the animation of specifications as well as for black-box testing of external programs. Our method is two-staged: first, the original formula is partitioned into test cases by transformation into a Horn-clause normal form (HCNF). Second, the test cases are analyzed for instances with constant terms satisfying the premises of the clauses. Particular emphasis is put on the control of test hypotheses and test hierarchies to avoid intractability. We applied our method to several examples, including AVL-trees and the red-black tree implementation in the standard library from SML/NJ.
-
symbolic test case generation for Primitive Recursive functions
FATES'04 Proceedings of the 4th international conference on Formal Approaches to Software Testing, 2004Co-Authors: Achim D Brucker, Burkhart WolffAbstract:We present a method for the automatic generation of test cases for HOL formulae containing Primitive Recursive predicates. These test cases can be used for the animation of specifications as well as for black-box testing of external programs. Our method is two-staged: first, the original formula is partitioned into test cases by transformation into a Horn-clause normal form (HCNF). Second, the test cases are analyzed for instances with constant terms satisfying the premises of the clauses. Particular emphasis is put on the control of test hypotheses and test hierarchies to avoid intractability. We applied our method to several examples, including AVL-trees and the red-black tree implementation in the standard library from SML/NJ.
Luca Paolini - One of the best experts on this subject based on the ideXlab platform.
-
A class of Recursive Permutations which is Primitive Recursive complete
Theoretical Computer Science, 2020Co-Authors: Luca Paolini, Mauro Piccolo, Luca RoversiAbstract:Abstract We focus on total functions in the theory of reversible computational models. We define a class of Recursive permutations, dubbed Reversible Primitive Permutations ( RPP ) which are computable invertible total endo-functions on integers, so a subset of total reversible computations. RPP is generated from five basic functions (identity, sign-change, successor, predecessor, swap), two notions of composition (sequential and parallel), one functional iteration and one functional selection. RPP is closed by inversion and it is expressive enough to encode Cantor pairing and the whole class of Primitive Recursive Functions.
-
On a Class of Reversible Primitive Recursive Functions and Its Turing-Complete Extensions
New Generation Computing, 2018Co-Authors: Luca Paolini, Mauro Piccolo, Luca RoversiAbstract:Reversible computing is both forward and backward deterministic. This means that a uniquely determined step exists from the previous computational configuration (backward determinism) to the next one (forward determinism) and vice versa. We present the reversible Primitive Recursive functions (RPRF), a class of reversible (endo-)functions over natural numbers which allows to capture interesting extensional aspects of reversible computation in a formalism quite close to that of classical Primitive Recursive functions. The class RPRF can express bijections over integers (not only natural numbers), is expressive enough to admit an embedding of the Primitive Recursive functions and, of course, its evaluation is effective. We also extend RPRF to obtain a new class of functions which are effective and Turing complete, and represent all Kleene’s \(\upmu \)-Recursive functions. Finally, we consider reversible recursion schemes that lead outside the reversible endo-functions.
-
A Class of Reversible Primitive Recursive Functions
Electronic Notes in Theoretical Computer Science, 2016Co-Authors: Luca Paolini, Mauro Piccolo, Luca RoversiAbstract:Reversible computing is bi-deterministic which means that its execution is both forward and backward deterministic, i.e. next/previous computational step is uniquely determined. Various approaches exist to catch its extensional or intensional aspects and properties. We present a class RPRF of reversible functions which holds at bay intensional aspects and emphasizes the extensional side of the reversible computation by following the style of Dedekind-Robinson Primitive Recursive Functions. The class RPRF is closed by inversion, can only express bijections on integers - not only natural numbers -, and it is expressive enough to simulate Primitive Recursive Functions, of course, in an effective way.
Achim D Brucker - One of the best experts on this subject based on the ideXlab platform.
-
FATES - Symbolic test case generation for Primitive Recursive functions
Formal Approaches to Software Testing, 2005Co-Authors: Achim D Brucker, Burkhart WolffAbstract:We present a method for the automatic generation of test cases for HOL formulae containing Primitive Recursive predicates. These test cases can be used for the animation of specifications as well as for black-box testing of external programs. Our method is two-staged: first, the original formula is partitioned into test cases by transformation into a Horn-clause normal form (HCNF). Second, the test cases are analyzed for instances with constant terms satisfying the premises of the clauses. Particular emphasis is put on the control of test hypotheses and test hierarchies to avoid intractability. We applied our method to several examples, including AVL-trees and the red-black tree implementation in the standard library from SML/NJ.
-
symbolic test case generation for Primitive Recursive functions
FATES'04 Proceedings of the 4th international conference on Formal Approaches to Software Testing, 2004Co-Authors: Achim D Brucker, Burkhart WolffAbstract:We present a method for the automatic generation of test cases for HOL formulae containing Primitive Recursive predicates. These test cases can be used for the animation of specifications as well as for black-box testing of external programs. Our method is two-staged: first, the original formula is partitioned into test cases by transformation into a Horn-clause normal form (HCNF). Second, the test cases are analyzed for instances with constant terms satisfying the premises of the clauses. Particular emphasis is put on the control of test hypotheses and test hierarchies to avoid intractability. We applied our method to several examples, including AVL-trees and the red-black tree implementation in the standard library from SML/NJ.
Emanuele Frittaion - One of the best experts on this subject based on the ideXlab platform.
-
Completeness of the Primitive Recursive $$\omega $$-rule
Archive for Mathematical Logic, 2020Co-Authors: Emanuele FrittaionAbstract:Shoenfield’s completeness theorem (1959) states that every true first order arithmetical sentence has a Recursive $$\omega $$-proof encodable by using Recursive applications of the $$\omega $$-rule. For a suitable encoding of Gentzen style $$\omega $$-proofs, we show that Shoenfield’s completeness theorem applies to cut free $$\omega $$-proofs encodable by using Primitive Recursive applications of the $$\omega $$-rule. We also show that the set of codes of $$\omega $$-proofs, whether it is based on Recursive or Primitive Recursive applications of the $$\omega $$-rule, is $$\varPi ^1_1$$ complete. The same $$\varPi ^1_1$$ completeness results apply to codes of cut free $$\omega $$-proofs.
-
completeness of the Primitive Recursive omega rule
Archive for Mathematical Logic, 2020Co-Authors: Emanuele FrittaionAbstract:Shoenfield’s completeness theorem (1959) states that every true first order arithmetical sentence has a Recursive $$\omega $$-proof encodable by using Recursive applications of the $$\omega $$-rule. For a suitable encoding of Gentzen style $$\omega $$-proofs, we show that Shoenfield’s completeness theorem applies to cut free $$\omega $$-proofs encodable by using Primitive Recursive applications of the $$\omega $$-rule. We also show that the set of codes of $$\omega $$-proofs, whether it is based on Recursive or Primitive Recursive applications of the $$\omega $$-rule, is $$\varPi ^1_1$$ complete. The same $$\varPi ^1_1$$ completeness results apply to codes of cut free $$\omega $$-proofs.
