Gröbner bases of characteristic ideals of LRS over UFD (Q1286694)

The authors investigate infinite and semi-infinite linear recurring sequences (LRS) over a unique factorization domain. They derive criteria for the associated ideal, the associated homogeneous ideal, and especially their Gröbner basis. It is shown that the minimal Gröbner basis of the homogeneous characteristic ideal of an LRS over a field has special properties. The steps of the Berlekamp-Massey algorithm may be reinterpreted as computing efficiently the minimal Gröbner basis of the ideal associated to the LRS.