Tropical recurrent sequences Abstract   Tropical recurrent sequences are introduced satisfying a given vector (being a tropical counterpart of classical linear recurrent sequences). We consider the case when Newton polygon of the vector has a single (bounded) edge. In this case there are periodic tropical recurrent sequences which are similar to classical linear recurrent sequences. A question is studied when there exists a nonperiodic tropical recurrent sequence satisfying a given vector, and partial answers are provided to this question. Also an algorithm is designed which tests existence of nonperiodic tropical recurrent sequences satisfying a given vector with integer coordinates. Finally, we introduce a tropical entropy of a vector, provide some bounds on it and extend this concept to tropical multivariable recurrent sequences.

Pointers in Recursion: Exploring the Tropics We translate the usual class of partialprimitive recursive functions to a pointer recursion framework, accessing actual input values via a pointer reading unitcost function. These pointer recursive functions classes are proven equivalent to the usual partialprimitive recursive functions. Complexitywise, this framework captures in a streamlined way most of the relevant subpolynomial classes. Pointer recursion with the safenormal tiering discipline of Bellantoni and Cook corresponds to polylogtime computation. We introduce a new, nonsize increasing tiering discipline, called tropical tiering. Tropical tiering and pointer recursion, used with some of the most common recursion schemes, capture the classes logspace, logspacepolylogtime, 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.