Repetitions in Text and Finite Automata
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F04%3A03106845" target="_blank" >RIV/68407700:21230/04:03106845 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Repetitions in Text and Finite Automata
Original language description
A general way to find repetitions of factors in a given text is shown. We start with a classification of repetitions. The general models for finding exact repetitions in one string and in a finite set of strings are introduced. It is shown that d-subsetscreated during determinization of nondeterministic factor automata contain all information concerning repetitions of factors. The principle of the analysis of d-subsets is then used for finding approximate repetitions using several distances for a general finite alphabet and for an ordered alphabet including the case of presence of don't care symbols. Complexity of finding repetitions is shown for exact repetitions in one string.
Czech name
Repetice v textu a konečné automaty
Czech description
Je popsána obecná metoda nalezení opakujících se podřetězců v daném textu. Nejdříve je uvedena klasifikace repetic. Dále je uveden obecný model nalezení přesných repetic v jednom a více textech. Je ukázáno, že d-množiny vzniklé při determinizaci nedeterministického faktorového automatu obsahují všechny informace, které se týkají repetic podřetězců. Princip analýzy těchto d-množin je potom použit pro nalezení přibližných repetic pro několik definic vzdáleností řetězců pro obecné i uspořádané abecedy. Jeuveden i případ tzv. don´t care symbolů. Složitost nalezení repetic je ukázána pro případ repetic v jednom textu.
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2004
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the Eindhoven FASTAR Days 2004
ISBN
0926-4515
ISSN
—
e-ISSN
—
Number of pages
46
Pages from-to
1-46
Publisher name
TU Eindhoven
Place of publication
Eindhoven
Event location
Eindhoven
Event date
Sep 3, 2004
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—