Vyhledávání přibližných pokrytí textu s použitím konečných automatů
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Searching Approximate Covers of Strings Using Finite Automata
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Searching Approximate Covers of Strings Using Finite Automata
Popis výsledku anglicky
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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GA201%2F06%2F1039" target="_blank" >GA201/06/1039: Analýza a zpracování textu</a><br>
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2009
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Workshop 09
ISBN
978-80-01-04286-1
ISSN
—
e-ISSN
—
Počet stran výsledku
2
Strana od-do
—
Název nakladatele
ČVUT
Místo vydání
Praha
Místo konání akce
Praha
Datum konání akce
16. 2. 2009
Typ akce podle státní příslušnosti
EUR - Evropská akce
Kód UT WoS článku
—