Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

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