Borders and Finite Automata

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F06%3A03120554" target="_blank" >RIV/68407700:21230/06:03120554 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Borders and Finite Automata

Original language description

A border of a string is a prefix of the string that is simultaneously its suffix. It is one of the basic stringology keystones used as a part of many algorithms in pattern matching, molecular biology, computer-assisted music analysis and others. The paper discusses automata-theoretical background of Iliopoulos's ALL_BORDERS algorithm that finds all borders of a string with don't care symbols. We show that ALL_BORDERS algorithm is a simulator of a finite automaton together with explaining the function ofthe automaton. We show that the simulated automaton accepts intersection of sets of prefixes and suffixes of the input string. Last but not least we define approximate borders. Based on the knowledge of the automata background of ALL_BORDERS algorithm we offer an automata-based algorithm that finds approximate borders with Hamming distance.

Czech name

Hranice v textu a konečné automaty

Czech description

Hranice textu je předpona, která je zároveň příponou. Jedná se o jeden ze základních stringologických pojmů, využívaných v rámci složitějších algoritmů vyhledávání, analýzy DNA sekvencí, hudby a dalších. Článek popisuje algoritmus ALL_BORDERS Iliopoulosea jeho kolegů na základě teorie konečných automatů. Tento algoritmus vyhledá všechny hranice všech předpon textu s don't care symboly. Ukazujeme, že algoritmus ALL_BORDERS simuluje činnost konečného automatu. Zároveň vysvětlujeme princip činnosti tohotoautomatu. S využitím znalosti souvislosti algoritmu a konečných automatů zobecníme algoritmus ALL_BORDERS pro vyhledávání přibližných hranic textu.

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)<br>S - Specificky vyzkum na vysokych skolach

Publication year

2006

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

Implementation and Application of Automata

ISBN

3-540-37213-X

ISSN

—

e-ISSN

—

Number of pages

11

Pages from-to

58-68

Publisher name

Springer-Verlag

Place of publication

Berlin

Event location

Taipei

Event date

Aug 21, 2006

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—