  Several algorithms for similarity search employ seeding techniques to quickly
discard very dissimilar regions. In this paper, we study theoretical properties
of lossless seeds, i.e., spaced seeds having full sensitivity. We prove that
lossless seeds coincide with languages of certain sofic subshifts, hence they
can be recognized by finite automata. Moreover, we show that these subshifts
are fully given by the number of allowed errors k and the seed margin l. We
also show that for a fixed k, optimal seeds must asymptotically satisfy l ~
m^(k/(k+1)).
