Searching Approximate Covers of Strings Using Finite Automata

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F09%3A03152997" target="_blank" >RIV/68407700:21230/09:03152997 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Searching Approximate Covers of Strings Using Finite Automata
Original language description
Cover is a type of a regularity of strings. A restricted approximate cover w of string T is a factor of T such that every position of T lies within some approximate occurrence of w in T. In this paper, a polynomial time and space algorithm for solving the problem of searching all approximate covers is presented. It searches for all restricted approximate covers of a string with given limited approximation using Hamming distance and it computes the smallest distance for each found cover. The solution isbased on a finite automata approach, that provides a straightforward way to design algorithms to many problems in stringology. Therefore it is shown that the set of problems solvable using finite automata includes the one studied in this paper.
Czech name
Vyhledávání přibližných pokrytí textu s použitím konečných automatů
Czech description
Pokrytí (cover) je druhem pravidelnosti textu. Vlastní pokrytí w textu T je faktor T takový že se každá pozice T nachází v nějakém přibližném výskytu w v T. V tomto článku je navržen algoritmus polynomiální v čase i paměti na vyhledávání všech přibližných pokrytí s danou maximální Hammingovou vzdáleností. Řešení je založeno na teorii konečných automatů, která umožňuje přímočarý návrh algoritmů na mnoho stringologických problémů.

Project
<a href="/en/project/GA201%2F06%2F1039" target="_blank" >GA201/06/1039: Text processing and analysis</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2009
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)