General algebra and its connections to computer science
Project goals
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.
Keywords
constraint satisfaction problemMaltsev conditionsnon-associative algebrascombinatorics on words
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 17 (SGA0201300005)
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
13-01832S
Alternative language
Project name in Czech
Obecná algebra a její souvislost s informatikou
Annotation in Czech
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ů.
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
BA - General mathematics
CEP - secondary branch
IN - Informatics
CEP - another secondary branch
—
10101 - Pure mathematics
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
The project focused on the complexity of CSP, universal algebra, combinatorics on words and automated methods of theorem proving. In some cases, significant progress has been made, such as resolving Valeriote conjecture or extending CSP to infinite sets. The project has thus significantly contributed to the deepening of universal algebra and CSP.
Solution timeline
Realization period - beginning
Feb 1, 2013
Realization period - end
Dec 31, 2017
Project status
U - Finished project
Latest support payment
Apr 11, 2017
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
CEP18-GA0-GA-U/02:1
Data delivery date
May 4, 2018
Finance
Total approved costs
6,852 thou. CZK
Public financial support
6,852 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
6 852 CZK thou.
Public support
6 852 CZK thou.
100%
Provider
Czech Science Foundation
CEP
BA - General mathematics
Solution period
01. 02. 2013 - 31. 12. 2017