Languages of lossless seeds

Autor: Karel Břinda
Jazyk: angličtina
Rok vydání: 2014
Předmět:
Zdroj: Electronic Proceedings in Theoretical Computer Science, Vol 151, Iss Proc. AFL 2014, Pp 139-150 (2014)
Druh dokumentu: article
ISSN: 2075-2180
DOI: 10.4204/EPTCS.151.9
Popis: 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)).
Databáze: Directory of Open Access Journals