All
All

What are you looking for?

All
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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