Clemente, Lorenzo ;
DontenBury, Maria ;
Mazowiecki, Filip ;
Pilipczuk, Michał
On Rational Recursive Sequences
Abstract
We study the class of rational recursive sequences (ratrec) over the rational numbers. A ratrec sequence is defined via a system of sequences using mutually recursive equations of depth 1, where the next values are computed as rational functions of the previous values. An alternative class is that of simple ratrec sequences, where one uses a single recursive equation, however of depth k: the next value is defined as a rational function of k previous values.
We conjecture that the classes ratrec and simple ratrec coincide. The main contribution of this paper is a proof of a variant of this conjecture where the initial conditions are treated symbolically, using a formal variable per sequence, while the sequences themselves consist of rational functions over those variables. While the initial conjecture does not follow from this variant, we hope that the introduced algebraic techniques may eventually be helpful in resolving the problem.
The class ratrec strictly generalises a wellknown class of polynomial recursive sequences (polyrec). These are defined like ratrec, but using polynomial functions instead of rational ones. One can observe that if our conjecture is true and effective, then we can improve the complexities of the zeroness and the equivalence problems for polyrec sequences. Currently, the only known upper bound is Ackermanian, which follows from results on polynomial automata. We complement this observation by proving a PSPACE lower bound for both problems for polyrec. Our lower bound construction also implies that the Skolem problem is PSPACEhard for the polyrec class.
BibTeX  Entry
@InProceedings{clemente_et_al:LIPIcs.STACS.2023.24,
author = {Clemente, Lorenzo and DontenBury, Maria and Mazowiecki, Filip and Pilipczuk, Micha{\l}},
title = {{On Rational Recursive Sequences}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {24:124:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772662},
ISSN = {18688969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17676},
URN = {urn:nbn:de:0030drops176763},
doi = {10.4230/LIPIcs.STACS.2023.24},
annote = {Keywords: recursive sequences, polynomial automata, zeroness problem, equivalence problem}
}
03.03.2023
Keywords: 

recursive sequences, polynomial automata, zeroness problem, equivalence problem 
Seminar: 

40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Issue date: 

2023 
Date of publication: 

03.03.2023 