Computer Science – Information Theory
Scientific paper
2009-11-29
Computer Science
Information Theory
This paper has been withdrawn by the author as the proof of Part (b) of Theorem 4.10(ii) is incorrect
Scientific paper
Let $s$ be a finite sequence over a field of length $n$. It is well-known that if $s$ satisfies a linear recurrence of order $d$ with non-zero constant term, then the reverse of $s$ also satisfies a recurrence of order $d$ (with coefficients in reverse order). A recent article of A. Salagean proposed an algorithm to find such a shortest 'two-way' recurrence -- which may be longer than a linear recurrence for $s$ of shortest length $\LC_n$. We give a new and simpler algorithm to compute a shortest two-way linear recurrence. First we show that the pairs of polynomials we use to construct a minimal polynomial iteratively are always relatively prime; we also give the extended multipliers. Then we combine degree lower bounds with a straightforward rewrite of a published algorithm due to the author to obtain our simpler algorithm. The increase in shortest length is $\max\{n+1-2\LC_n,0\}$.
No associations
LandOfFree
Shortest Two-way Linear Recurrences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Shortest Two-way Linear Recurrences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shortest Two-way Linear Recurrences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-150841