The complexity of initial state recovery for a class of filter generators

A recovery problem for the initial state of the $m$-th order recurrent sequence from the output values of filter function $F$. Under natural conditions on the feedback function $f$ and filter function $F$ the complexity of initial state recovery from linear (in $m$) number of output values is shown to be linear in $m$. Coefficients of these linear functions are defined by the cardinalities of alphabet of output values, alphabet of input sequence elements and numbers of essential arguments of functions $f$ and $F$.