A class of recursive permutations which is primitive recursive complete

DOI10.1016/J.TCS.2019.11.029zbMATH Open1481.03031OpenAlexW2990494648WikidataQ126641588 ScholiaQ126641588MaRDI QIDQ1989331FDOQ1989331

Luca Roversi, Mauro Piccolo, Luca Paolini

Publication date: 21 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2318/1734163

zbMATH Keywords

reversible computationrecursion theoryprimitive recursive functionscomputable permutationsunconventional computing models

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Recursive functions and relations, subrecursive hierarchies (03D20)

Cites Work

• Towards a Reversible Functional Language
• Information effects
• On quantum lambda calculi: a foundational perspective
• Title not available (Why is that?)
• Title not available (Why is that?)
• Mathematics of Program Construction
• Title not available (Why is that?)
• Title not available (Why is that?)
• Logical Reversibility of Computation
• Reversible computing and cellular automata -- a survey
• Title not available (Why is that?)
• AN ELEMENTARY THEORY OF THE CATEGORY OF SETS
• Title not available (Why is that?)
• What Do Reversible Programs Compute?
• On reversible Turing machines and their function universality
• Reversible Turing Machines and Polynomial Time Reversibly Computable Functions
• Classical recursion theory. The theory of functions and sets of natural numbers
• Diagram rewriting and operads
• Title not available (Why is that?)
• Title not available (Why is that?)
• Higher-dimensional word problems with applications to equational logic
• Towards an algebraic theory of Boolean circuits.
• Time/Space Trade-Offs for Reversible Computation
• Title not available (Why is that?)
• Generation of invertible functions
• Linear programs in a simple reversible language.
• Title not available (Why is that?)
• A class of reversible primitive recursive functions
• On primitive recursive permutations and their inverses
• General Recursive Functions
• On the representation of partial recursive functions as superpositions
• Title not available (Why is that?)
• The pillars of computation theory. State, encoding, nondeterminism
• Representation of partial recursive functions with certain conditions in the form of superpositions
• Reversibility and adiabatic computation: trading time and space for energy
• Interactions between computer science and biology
• Ricercar: A Language for Describing and Rewriting Reversible Circuits with Ancillae and Its Permutation Semantics
• A Certified Study of a Reversible Programming Language

Cited In (6)

• Towards a taxonomy for reversible computation approaches
• Certifying expressive power and algorithms of reversible primitive permutations with \textsf{Lean}
• Splitting Recursion Schemes into Reversible and Classical Interacting Threads
• Algorithmically expressive, always-terminating model for reversible computation
• Title not available (Why is that?)
• Certifying algorithms and relevant properties of reversible primitive permutations with \textsf{Lean}

Uses Software

• Theseus

   Recommendations

• Composability of permutation classes 👍 👎
• An algorithm for deciding the finiteness of the number of simple permutations in permutation classes 👍 👎
• Combinatorial specification of permutation classes 👍 👎
• Infinite classes of generalised complete permutations 👍 👎
• A recursive construction of t -wise uniform permutations 👍 👎
• An algorithm computing combinatorial specifications of permutation classes 👍 👎
• Рекурсивно-порождаемые перестановки двоичного пространства 👍 👎
• Title not available (Why is that?) 👍 👎
• Several classes of complete permutation polynomials 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: A class of recursive permutations which is primitive recursive complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1989331)