String matching in text
Project goals
The oldest string pattern matching algorithms have been known since seventies. The classification of pattern matching algorithms and formal model of algorithms for their solution , based on finite automata, was found last year.Consequently, there exist algorithms with linear time complexity for all classified pattern matching problems. The project is focused on the developingof these ideas in the following directions: the finding of realist estimation of memory complexity for particular problems, the valuation of existing algorithms as simulators of nondeterministic finite automata, the finding of similar algorithms based on counter-direct searching (from right to left) ,the finding of effective parallel implementation of particular algorithms.
Keywords
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
—
Main participants
České vysoké učení technické v Praze / Fakulta elektrotechnická
Contest type
—
Contract ID
—
Alternative language
Project name in Czech
Vyhledávání v textu
Annotation in Czech
Nejstarší algoritmy vyhledávání v textu jsou známy již od sedmdesátých let. V minulém roce se podařilo nalézt klasifikaci vyhledávacích problémů a formální modely algoritmů na jejich řešení založené na konečných automatech. Z toho plyne, že pro všechny vyhledávací problémy zahrnuté do uvedené klasifikace existují algoritmy s lineární časovou složitostí. Projekt je zaměřen na rozpracování uvedených myšlenek v těchto směrech: nalezení realistických odhadů paměťové složitosti pro jednotlivé úkoly, hodnocení existujících algoritmů jako simulátorů nedeterministických konečných automatů, nalezení podobné skupiny modelů algoritmů na protisměrné vyhledávání, nalezení efektivní paralelní implementace jednotlivých algoritmů.
Scientific branches
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
Výstupem projektu je formulace a využití semihomogenních nedeterministických konečných automatů pro hledání v textech. Byly nalezeny teoretické modely a odvozena složitost daných automatů. Jde o původní výsledky, které mají dalekosáhlý význam pro praxi.
Solution timeline
Realization period - beginning
Jan 1, 1998
Realization period - end
Jan 1, 2000
Project status
U - Finished project
Latest support payment
—
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP/2001/GA0/GA01GA/U/N/9:4
Data delivery date
—
Finance
Total approved costs
1,056 thou. CZK
Public financial support
1,006 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
1 056 CZK thou.
Public support
1 006 CZK thou.
0%
Provider
Czech Science Foundation
CEP
JC - Computer hardware and software
Solution period
01. 01. 1998 - 01. 01. 2000