Finite Linear Recurring Sequences and Homogeneous Ideals

Joachim Althaler, Arne Dür

Publikation: Beitrag in FachzeitschriftArtikel

9 Zitate (Scopus)

Abstract

The linear recurrence relations satisfied by finitely many sequences of finite length over a ground field are described by homogeneous ideals in the polynomial ring in two variables by using Macaulay's theory of inverse systems. The class of these ideals is shown to be precisely the class of homogeneous primary ideals the associated prime of which is the irrelevant maximal ideal. In the case of a single sequence, the classical Berlekamp-Massey algorithm for linear feedback shift register synthesis can be applied to obtain a minimal Gröbner basis of the ideal. The case of multiple sequences is reduced to the case of single sequences by ideal intersection, and the set of all linear recurrence relations of minimal order for the given sequences is generated by the low degree polynomials of the Gröbner basis.

OriginalspracheEnglisch
Seiten (von - bis)377-390
Seitenumfang14
FachzeitschriftApplicable Algebra in Engineering, Communication and Computing 7
Jahrgang7
Ausgabenummer5
DOIs
PublikationsstatusVeröffentlicht - Aug 1996

Fingerprint

Untersuchen Sie die Forschungsthemen von „Finite Linear Recurring Sequences and Homogeneous Ideals“. Zusammen bilden sie einen einzigartigen Fingerprint.

Zitieren