Finite Automata Approach to Computing All Seeds of Strings with the Smallest Hamming Distance

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F09%3A03156152" target="_blank" >RIV/68407700:21230/09:03156152 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Finite Automata Approach to Computing All Seeds of Strings with the Smallest Hamming Distance

Original language description

Seed is a type of a regularity of strings. A restricted approximate seed w of string T is a factor of T such that w covers a superstring of T under some distance rule. In this paper, the problem of all restricted seeds with the smallest Hamming distanceis studied and a polynomial time and space algorithm for solving the problem is presented. It searches for all restricted approximate seeds of a string with given limited approximation using Hamming distance and it computes the smallest distance for eachfound seed. The solution is based on a finite (suffix) 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

Využití konečných automatů při vyhledávání všech jader textu s minimální Hammingovou vzdáleností

Czech description

Jádro je druhem pravidelnosti textových řetězců. Vlastní přibližné jádro w řetězce T je jeho faktor w takový, že w pokrývá nějaký nadřetězec T. V tomto článku je řešen problém vyhledávání všech vlastních přibližných jader ř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 (sufixový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 jader.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

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ů

Name of the periodical

International Journal of Computer Science

ISSN

1819-9224

e-ISSN

—

Volume of the periodical

36

Issue of the periodical within the volume

2

Country of publishing house

HK - HONG KONG

Number of pages

10

Pages from-to

—

UT code for WoS article

—

EID of the result in the Scopus database

—