  Given a multi-index sequence $$\sigma$$, we present a new efficient algorithm
to compute generators of the linear recurrence relations between the terms of
$$\sigma$$. We transform this problem into an algebraic one, by identifying
multi-index sequences, multivariate formal power series and linear functionals
on the ring of multivariate polynomials. In this setting, the recurrence
relations are the elements of the kerne l$I$\sigma$$ of the Hankel operator
$H$\sigma$$ associated to $$\sigma$$. We describe the correspondence between
multi-index sequences with a Hankel operator of finite rank and Artinian
Gorenstein Algebras. We show how the algebraic structure of the Artinian
Gorenstein algebra $A$\sigma$$ associated to the sequence $$\sigma$$ yields the
structure of the terms $\sigma$$\alpha$ for all $$\alpha$ $\in$ N n$. This
structure is explicitly given by a border basis of $A$\sigma$$, which is
presented as a quotient of the polynomial ring $K[x 1 ,. .. , xn$] by the
kernel $I$\sigma$$ of the Hankel operator $H$\sigma$$. The algorithm provides
generators of $I$\sigma$$ constituting a border basis, pairwise orthogonal
bases of $A$\sigma$$ and the tables of multiplication by the variables in these
bases. It is an extension of Berlekamp-Massey-Sakata (BMS) algorithm, with
improved complexity bounds. We present applications of the method to different
problems such as the decomposition of functions into weighted sums of
exponential functions, sparse interpolation, fast decoding of algebraic codes,
computing the vanishing ideal of points, and tensor decomposition. Some
benchmarks illustrate the practical behavior of the algorithm.
