2026-07-22T11:07:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11652 2024-03-06T10:48:42Z ddc:004 open_access

A Robust Class of Linear Recurrence Sequences Barloy, Corentin Fijalkow, Nathanaël Lhote, Nathan Mazowiecki, Filip linear recurrence sequences weighted automata cost-register automata We introduce a subclass of linear recurrence sequences which we call poly-rational sequences because they are denoted by rational expressions closed under sum and product. We show that this class is robust by giving several characterisations: polynomially ambiguous weighted automata, copyless cost-register automata, rational formal series, and linear recurrence sequences whose eigenvalues are roots of rational numbers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Corentin Barloy and Nathanaël Fijalkow and Nathan Lhote and Filip Mazowiecki 2020 Is Part Of LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2020.9 urn:nbn:de:0030-drops-116521 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.9 eng https://creativecommons.org/licenses/by/3.0/legalcode