A representation theorem for (q-)holonomic sequences

作者：

Highlights：

• We prove representation theorems for sequences with recurrence relations.

• (q-)Holonomic sequences are captured by appropriate logical interpretations.

• Representations based on positional weights of words in regular languages are shown.

• A weightless sparse-structures representation is given for holonomic sequences only.

摘要

•We prove representation theorems for sequences with recurrence relations.•(q-)Holonomic sequences are captured by appropriate logical interpretations.•Representations based on positional weights of words in regular languages are shown.•A weightless sparse-structures representation is given for holonomic sequences only.

论文关键词：Holonomic sequences,q-Holonomic sequences,Positional weights on words,Regular languages,Monadic Second Order Logic

论文评审过程：Received 24 November 2010, Revised 9 January 2013, Accepted 4 May 2013, Available online 17 May 2013.

论文官网地址：https://doi.org/10.1016/j.jcss.2013.05.004