Algebraická teorie jazyků pro nekonečné stromy

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

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.

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 <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)

10101 - Pure mathematics<br>10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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.

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

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

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č