Pointers in Recursion: Exploring the Tropics

Paulin Jacobé de Naurois (1)

1 LIPN - Laboratoire d'Informatique de Paris-Nord

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 tier-ing is expressed directly in the syntax of the function algebras, yielding the tropical recursive function algebras.

Domaines: Complexité [cs.CC]

Paulin Jacobé de Naurois. Pointers in Recursion: Exploring the Tropics. 2019. ⟨hal-01934791v2⟩