Searching All Approximate Covers and Their Distance using Finite Automata

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F08%3A03146046" target="_blank" >RIV/68407700:21230/08:03146046 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Searching All Approximate Covers and Their Distance 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, the problem of all restricted smallest distance approximate covers of a string is studied and a polynomial time and space algorithm for solving the problem 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 is based 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 finiteautomata includes the one studied in this paper.

Czech name

Vyhledávání všech přibližných pokrytí textu a jejich vzdáleností s použitím konečných automatů

Czech description

Pokrytí je druhem pravidelnosti textových řetězců. Vlastní přibližné pokrytí w řetězce T je jeho faktor w takový, že se každá pozice řetězce T nachází v nějakém přibližném výskytu faktoru w v řetězci T. V tomto článku je řešen problém vyhledávání všech vlastních přibližných pokrytí řetězce a jejich skutečných vzdáleností a dále je ukázán algoritmus polynomiální v čase i paměti. Vyhledávání je přibližné a je uvažována zadaná maximální Hammingova vzdálenost. Řešení je založeno na teorii konečných automatů, která umožňuje přímočarý návrh stringologických algoritmů. Je tak ukázáno, že množina problémů řešitelných s pomocí konečných automatů obsahuje i vyhledávání přibližných pokrytí.

Type

D - Article in proceedings

CEP classification

IN - Informatics

OECD FORD branch

—

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

2008

Confidentiality

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

Article name in the collection

Information Technologies - Applications and Theory

ISBN

978-80-969184-9-2

ISSN

—

e-ISSN

—

Number of pages

6

Pages from-to

—

Publisher name

Univerzita P. J. Šafárika

Place of publication

Košice

Event location

Hrebinok, Vysoké Tatry

Event date

Sep 22, 2008

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—