Algebraic Language Theory for Infinite Trees
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 21 (SGA0201700001)
Main participants
Masarykova univerzita / Fakulta informatiky
Contest type
VS - Public tender
Contract ID
17-01035S
Alternative language
Project name in Czech
Algebraická teorie jazyků pro nekonečné stromy
Annotation in Czech
Algebraická teorie jazyků poskytuje alternativní přístup k popisu regulárních jazyků pomocí algebraických objektů místo automatů. Její výhodou je, že umožňuje používat sofistikované algebraické nástroje k analýze jazyků. Jednou z oblastí, kde algebraická teorie jazyků byla dosud velmi úspěšná, je oblast návrhu rozhodovacích algoritmů pro podtřídy regulárních jazyků, což znamená rozhodovat, zda daný regulární jazyk náleží popsané třídě. Příkladem je klasický výsledek Schützenbergera, který umožňuje rozhodnout, zda zadaný jazyk je definovatelný v logice prvního řádu. Doposud známe dobře popsané algebraické teorie jazyků pro konečná a nekonečná slova. V oblasti konečných slov existuje několik soupeřících algebraických teorií jazyků, avšak v oblasti nekonečných stromů je vývoj doposud v plenkách. Cílem našeho projektu je vyvinout algebraickou teorii pro jazyky nekonečných stromů. V druhém kroku plánujeme vznikající teorii využít pro získání prvních charakterizačních výsledků, zpočátku pro jednoduché logiky jako EF a postupně mířit k plnému cíli charakterizace logiky prvního řádu.
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
IN - Informatics
CEP - secondary branch
BA - General mathematics
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>)
10101 - Pure mathematics<br>10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
This is a highly theoretical project, dealing with so-called "tree algebras". New theoretical frameworks have been generated but its importance is difficult to assess. Its importance for future applications is also not demonstrated. There is only one conference publication and one accepted journal paper. Part of the money has not been spent.
Solution timeline
Realization period - beginning
Jan 1, 2017
Realization period - end
Dec 31, 2019
Project status
U - Finished project
Latest support payment
Apr 3, 2019
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
CEP20-GA0-GA-U/02:1
Data delivery date
Jul 23, 2020
Finance
Total approved costs
2,731 thou. CZK
Public financial support
1,985 thou. CZK
Other public sources
481 thou. CZK
Non public and foreign sources
0 thou. CZK