@article{KotekMakowsky:JCSS:2014,
    Abstract = {Chomsky and Sch{\"u}tzenberger showed in 1963 that the sequence 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) which satisfies a linear recurrence relation with constant coefficients can be represented as 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.},
    Author = {Kotek, T. and Makowsky, J. A.},
    File = {A representation theorem for (q-)holonomic sequences - 1-s2.0-S0022000013000937-main - a - t.pdf},
    ISSN = {0022-0000},
    Journal = {Journal of Computer and System Sciences},
    Keywords = {Holonomic sequences, -Holonomic sequences, Positional weights on words, Regular languages, Monadic Second Order Logic},
    Number = {2},
    Pages = {363--374},
    Title = {A representation theorem for (q-)holonomic sequences},
    URL = {http://www.sciencedirect.com/science/article/pii/S0022000013000937},
    Volume = {80},
    Year = {2014},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0022000013000937},
    bdsk-url-2 = {https://doi.org/10.1016/j.jcss.2013.05.004},
    date-added = {2020-10-04 09:46:01 +0200},
    date-modified = {2023-08-23 11:43:18 +0200},
    doi = {10.1016/j.jcss.2013.05.004}
}

@article{KotekMakowsky:JCSS:2014, Abstract = {Chomsky and Sch{\"u}tzenberger showed in 1963 that the sequence 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) which satisfies a linear recurrence relation with constant coefficients can be represented as 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.}, Author = {Kotek, T. and Makowsky, J. A.}, File = {A representation theorem for (q-)holonomic sequences - 1-s2.0-S0022000013000937-main - a - t.pdf}, ISSN = {0022-0000}, Journal = {Journal of Computer and System Sciences}, Keywords = {Holonomic sequences, -Holonomic sequences, Positional weights on words, Regular languages, Monadic Second Order Logic}, Number = {2}, Pages = {363--374}, Title = {A representation theorem for (q-)holonomic sequences}, URL = {http://www.sciencedirect.com/science/article/pii/S0022000013000937}, Volume = {80}, Year = {2014}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0022000013000937}, bdsk-url-2 = {https://doi.org/10.1016/j.jcss.2013.05.004}, date-added = {2020-10-04 09:46:01 +0200}, date-modified = {2023-08-23 11:43:18 +0200}, doi = {10.1016/j.jcss.2013.05.004} }