Finding a minimal set of linear recurring relations capable of generating a given finite two-dimensional array

DOI10.1016/S0747-7171(88)80033-6zbMath0647.68044MaRDI QIDQ1104749

Shojiro Sakata

Publication date: 1988

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

Gröbner basespolynomial idealscomplexity of computationlinear recurring relationsBerlekamp- Massey algorithmfinite two-dimensional arraylinear feedback shift-register

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Finite fields and commutative rings (number-theoretic aspects) (11T99) Arithmetic codes (94B40)

Related Items

Polynomial-division-based algorithms for computing linear recurrence relations, Polynomial-exponential decomposition from moments, Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences, Linear recurring sequences over modules, Linear recurring sequences over rings and modules, In-depth comparison of the Berlekamp-Massey-Sakata and the Scalar-FGLM algorithms: the adaptive variants, Theory behind quantum error correcting codes: an overview, Sparse FGLM algorithms, Two-dimensional shift register synthesis and Gröbner bases for polynomial ideals over an integer residue ring, On inverse systems and squarefree decomposition of zero-dimensional polynomial ideals, Decoding up to 4 errors in hyperbolic-like abelian codes by the Sakata algorithm, Gröbner basis approach to list decoding of algebraic geometry codes, A behavioral approach to identifiability of 2D scalar systems, Solving the FCSR synthesis problem for multi-sequences by lattice basis reduction, Linear feedback shift registers and the minimal realization problem, Solving a congruence on a graded algebra by a subresultant sequence and its application, Extension of the Berlekamp-Massey algorithm to N dimensions, Unnamed Item, Multidimensional linear complexity analysis of periodic arrays, Guessing Gröbner bases of structured ideals of relations of sequences, On evaluating multivariate polynomials over finite fields, A type of recurring relation on sequences and efficient decoding of a class of algebraic-geometric codes. I, Finding recursions for multidimensional arrays, Recursive partial realization for 2-D data arrays

Cites Work

• Unnamed Item
• Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems
• On determining the independent point set for doubly periodic arrays and encoding two-dimensional cyclic codes and their duals
• A theory of two-dimensional cyclic codes
• General theory of doubly periodic arrays over an arbitrary finite field and its applications
• Impulse response arrays of discrete-space systems over a finite field
• Shift-register synthesis and BCH decoding