Using Finite Automata Approach for Searching Approximate Seeds of Strings

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F10%3A00170021" target="_blank" >RIV/68407700:21240/10:00170021 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-90-481-3517-2_27" target="_blank" >http://dx.doi.org/10.1007/978-90-481-3517-2_27</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Using Finite Automata Approach for Searching Approximate Seeds of Strings

Popis výsledku v původním jazyce

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 searching of all restricted seeds with the smallest Hamming distance is 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 each found 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.

Název v anglickém jazyce

Using Finite Automata Approach for Searching Approximate Seeds of Strings

Popis výsledku anglicky

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 searching of all restricted seeds with the smallest Hamming distance is 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 each found 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.

Druh

C - Kapitola v odborné knize

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F09%2F0807" target="_blank" >GA201/09/0807: Analýza a zpracování řetězců a stromů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2010

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ů

Název knihy nebo sborníku

Intelligent Automation and Computer Engineering

ISBN

978-90-481-3516-5

Počet stran výsledku

14

Strana od-do

347-360

Počet stran knihy

501

Název nakladatele

Springer

Místo vydání

New York

Kód UT WoS kapitoly

—