Hranice v textu a konečné automaty
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Borders and Finite Automata
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Borders and Finite Automata
Popis výsledku anglicky
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.
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)<br>S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2006
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
Implementation and Application of Automata
ISBN
3-540-37213-X
ISSN
—
e-ISSN
—
Počet stran výsledku
11
Strana od-do
58-68
Název nakladatele
Springer-Verlag
Místo vydání
Berlin
Místo konání akce
Taipei
Datum konání akce
21. 8. 2006
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—