Reversible Programming Languages Capturing Complexity Classes

We argue that there is a link between implicit computational complexity theory and the theory of reversible computation. We show that the complexity classes [Formula: see text] and [Formula: see text] can be captured by inherently reversible programming languages.

Detalles Bibliográficos
Autor principal: Kristiansen, Lars
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7345302/
http://dx.doi.org/10.1007/978-3-030-52482-1_6
_version_ 1783556149514076160
author Kristiansen, Lars
author_facet Kristiansen, Lars
author_sort Kristiansen, Lars
collection PubMed
description We argue that there is a link between implicit computational complexity theory and the theory of reversible computation. We show that the complexity classes [Formula: see text] and [Formula: see text] can be captured by inherently reversible programming languages.
format Online
Article
Text
id pubmed-7345302
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-73453022020-07-09 Reversible Programming Languages Capturing Complexity Classes Kristiansen, Lars Reversible Computation Article We argue that there is a link between implicit computational complexity theory and the theory of reversible computation. We show that the complexity classes [Formula: see text] and [Formula: see text] can be captured by inherently reversible programming languages. 2020-06-17 /pmc/articles/PMC7345302/ http://dx.doi.org/10.1007/978-3-030-52482-1_6 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Kristiansen, Lars
Reversible Programming Languages Capturing Complexity Classes
title Reversible Programming Languages Capturing Complexity Classes
title_full Reversible Programming Languages Capturing Complexity Classes
title_fullStr Reversible Programming Languages Capturing Complexity Classes
title_full_unstemmed Reversible Programming Languages Capturing Complexity Classes
title_short Reversible Programming Languages Capturing Complexity Classes
title_sort reversible programming languages capturing complexity classes
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7345302/
http://dx.doi.org/10.1007/978-3-030-52482-1_6
work_keys_str_mv AT kristiansenlars reversibleprogramminglanguagescapturingcomplexityclasses

Ejemplares similares