2026-07-26T04:14:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10536 2024-03-06T10:46:10Z ddc:004 open_access

Pointers in Recursion: Exploring the Tropics Jacobé de Naurois, Paulin Implicit Complexity Recursion Theory We translate the usual class of partial/primitive recursive functions to a pointer recursion framework, accessing actual input values via a pointer reading unit-cost function. These pointer recursive functions classes are proven equivalent to the usual partial/primitive recursive functions. Complexity-wise, this framework captures in a streamlined way most of the relevant sub-polynomial classes. Pointer recursion with the safe/normal tiering discipline of Bellantoni and Cook corresponds to polylogtime computation. We introduce a new, non-size increasing tiering discipline, called tropical tiering. Tropical tiering and pointer recursion, used with some of the most common recursion schemes, capture the classes logspace, logspace/polylogtime, ptime, and NC. Finally, in a fashion reminiscent of the safe recursive functions, tropical tiering is expressed directly in the syntax of the function algebras, yielding the tropical recursive function algebras. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paulin Jacobé de Naurois 2019 Is Part Of LIPIcs, Volume 131, 4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSCD.2019.29 urn:nbn:de:0030-drops-105360 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2019.29 eng https://creativecommons.org/licenses/by/3.0/legalcode