Linear complexity of sequences over arbitrary symbols and constructions of sequences over GF(pk) whose characteristic polynomial is over GF(p)

We propose an appropriate approach of defining the linear complexity of sequences over an unknown symbol set. We are able to characterize those p-ary sequences whose k-tuple versions now over GF(p^k) have the same characteristic polynomial as the original with respect to any basis. This leads to a construction of p^k-ary sequences whose characteristic polynomial is essentially over GF(p).