Chronological Overview 
 Type-Hierarchical Overview 
Formal Methods in Computing
(Most of the papers antecedent to 1995
are not included in the list)
FRAMES  NO FRAME 

paolini2020tcs (Article)
Author(s) Luca Paolini, Mauro Piccolo and Luca Roversi
Title« A class of Recursive Permutations which is Primitive Recursive complete »
JournalTheoretical Computer Science
Volume813
Page(s)218 - 233
Year2020
ISSN number0304-3975
URLhttp://www.sciencedirect.com/science/article/pii/S0304397519307558
Abstract & Keywords
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.

Keywords: Reversible computation, Unconventional computing models, Computable permutations, Primitive recursive functions, Recursion theory

BibTeX code

@article{paolini2020tcs,
  volume = {813},
  author = {Luca Paolini and Mauro Piccolo and Luca Roversi},
  issn = {0304-3975},
  keywords = {Reversible computation, Unconventional computing models,
              Computable permutations, Primitive recursive functions, Recursion
              theory},
  url = {http://www.sciencedirect.com/science/article/pii/S0304397519307558},
  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.},
  title = {A class of Recursive Permutations which is Primitive Recursive
           complete},
  pages = {218 - 233},
  journal = {Theoretical Computer Science},
  doi = {https://doi.org/10.1016/j.tcs.2019.11.029},
  year = {2020},
}


 Chronological Overview 
 Type-Hierarchical Overview 
Formal Methods in Computing
(Most of the papers antecedent to 1995
are not included in the list)
FRAMES  NO FRAME 

This document was generated by bib2html 3.3.
(Modified by Luca Paolini, under the GNU General Public License)

Valid HTML 4.01!