Obecná algebra a její souvislost s informatikou
Cíle projektu
Cílem navrženého projektu je vyřešit vybrané problémy na pomezí obecné algebry a teoretické informatiky. Práce se soustředí na následující oblasti: složitost problému splnitelnosti omezení (hypotéza Federa a Vardiho, jemnější složitostní klasifikace CSP, různé varianty CSP), struktura univerzálních algeber a mal'cevské podmínky (Valeriotova hypotéza, teorie absorpce), struktura samodistributivních a mediálních algeber (zejména teorie módů a teorie quandlů a její vazba na teorii uzlů), rovnice na slovech (binární ekvivalenční množiny, binární Postův korespondenční problém, nezávislé systémy rovnic). Jistou roli v rámci výzkumu budou hrát automatické metody a zpětná vazba autorům použitých počítačových systémů.
Klíčová slova
constraint satisfaction problemMaltsev conditionsnon-associative algebrascombinatorics on words
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
Standardní projekty 17 (SGA0201300005)
Hlavní účastníci
Univerzita Karlova / Matematicko-fyzikální fakulta
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
13-01832S
Alternativní jazyk
Název projektu anglicky
General algebra and its connections to computer science
Anotace anglicky
The aim of the project is to solve selected problems in areas on the border of general algebra and computer science. We will focus on the following problems: complexity of the constraint satisfaction problems (the Feder-Vardi conjecture, finer complexity classification of the CSPs, various variants of CSP), the structure of universal algebras and Maltsev conditions (the Valeriote conjecture, absorption theory), the structure of selfdistributive and medial algebras (focusing on modes, and on quandles and their relation to knot theory), and word equations (binary equality languages, binary Post Correspondence Problem, independent systems of equations). A part of our research will be supported by automated methods and we plan to provide feedback to the developers of the computer systems we shall use.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
CEP - hlavní obor
BA - Obecná matematika
CEP - vedlejší obor
IN - Informatika
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
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Zhodnocení výsledků projektu
Projekt se soustředil na složitost CSP, univerzální algebru, kombinatoriku na slovech a automatické metody dokazovaní. V některých případech bylo dosaženo významného pokroku, jako je např. řešení Valeriotovy domněnky nebo rozšíření záběru CSP na nekonečné množiny. Projekt tak významně přispěl k prohloubení univerzální algebry a CSP.
Termíny řešení
Zahájení řešení
1. 2. 2013
Ukončení řešení
31. 12. 2017
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
11. 4. 2017
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
CEP18-GA0-GA-U/02:1
Datum dodání záznamu
4. 5. 2018
Finance
Celkové uznané náklady
6 852 tis. Kč
Výše podpory ze státního rozpočtu
6 852 tis. Kč
Ostatní veřejné zdroje financování
0 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Uznané náklady
6 852 tis. Kč
Statní podpora
6 852 tis. Kč
0%
Poskytovatel
Grantová agentura České republiky
CEP
BA - Obecná matematika
Doba řešení
01. 02. 2013 - 31. 12. 2017