کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429827 | 687688 | 2014 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A representation theorem for (q-)holonomic sequences A representation theorem for (q-)holonomic sequences](/preview/png/429827.png)
• 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.
Chomsky and Schützenberger showed in 1963 that the sequence dL(n)dL(n), which counts the number of words of a given length n in a regular language L, satisfies a linear recurrence relation with constant coefficients for n , i.e., it is C-finite. It follows that every sequence s(n)s(n) which satisfies a linear recurrence relation with constant coefficients can be represented as dL1(n)−dL2(n)dL1(n)−dL2(n) for two regular languages. We view this as a representation theorem for C-finite sequences. Holonomic or P-recursive sequences are sequences which satisfy a linear recurrence relation with polynomial coefficients. q-Holonomic sequences are the q-analog of holonomic sequences. In this paper we prove representation theorems of holonomic and q-holonomic sequences based on position specific weights on words, and for holonomic sequences, without using weights, based on sparse regular languages.
Journal: Journal of Computer and System Sciences - Volume 80, Issue 2, March 2014, Pages 363–374