String matching in text
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
R&D category
—
CEP classification - main branch
JC - Computer hardware and software
CEP - secondary branch
—
CEP - another secondary branch
—
OECD FORD - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
20206 - Computer hardware and architecture
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