Algebraická teorie jazyků pro nekonečné stromy
Cíle projektu
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.
Klíčová slova
algebraic-language-theorymonadic-second-order-logicinfinite-treesregular-languages
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
Standardní projekty 21 (SGA0201700001)
Hlavní účastníci
Masarykova univerzita / Fakulta informatiky
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
17-01035S
Alternativní jazyk
Název projektu anglicky
Algebraic Language Theory for Infinite Trees
Anotace anglicky
Algebraic Language Theory provides an alternative approach for describing regular languages that uses algebraic objects instead of automata. Its advantages are that one can use sophisticated algebraic tools to analyse languages. One area where Algebraic Language Theory has been particularly successful is in devising decision procedures for subclasses of regular languages, i.e., for the question whether a given regular language belongs to the class in question. For instance, a classical result of Schützenberger allows one to decide whether a given language is definable in first-order logic. So far there are well-developed algebraic theories for languages of finite and infinite words. There are also candidates for languages of finite trees, but the theory for infinite trees is still in its infancy. The goal of this project is to develop an algebraic theory for languages of infinite trees. In a second step, we aim to use the emerging framework for first characterisation results starting with simple logics like EF and ultimately aiming at a characterisation of full first-order logic.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
CEP - hlavní obor
IN - Informatika
CEP - vedlejší obor
BA - Obecná matematika
CEP - další vedlejší obor
—
OECD FORD - odpovídající obory
(dle převodníku)10101 - Pure mathematics
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Hodnocení dokončeného projektu
Hodnocení poskytovatelem
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Zhodnocení výsledků projektu
Jedná se o velmi teoretický projekt, zabývající se tak zvanými "stromovými algebrami". Byly vytvořeny nové teoretické poznatky charakterizující tyto matematické struktury, jejich význam je ovšem obtížné posoudit. Nebyl demonstrován ani jejich význam pro aplikace. Uznatelným výsledkem projektu je pouze jeden konferenční článek a jeden časopisecký článek. Přidělené prostředky nebyly zcela využity.
Termíny řešení
Zahájení řešení
1. 1. 2017
Ukončení řešení
31. 12. 2019
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
3. 4. 2019
Dodání dat do CEP
Důvěrnost údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Systémové označení dodávky dat
CEP20-GA0-GA-U/02:1
Datum dodání záznamu
23. 7. 2020
Finance
Celkové uznané náklady
2 731 tis. Kč
Výše podpory ze státního rozpočtu
1 985 tis. Kč
Ostatní veřejné zdroje financování
481 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Základní informace
Uznané náklady
2 731 tis. Kč
Statní podpora
1 985 tis. Kč
72%
Poskytovatel
Grantová agentura České republiky
CEP
IN - Informatika
Doba řešení
01. 01. 2017 - 31. 12. 2019