Characterization and tractability of constraint languages via logical methods
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202500001
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
25-16324S
Alternative language
Project name in Czech
Charakterizace a efektivní řešitelnost constraintových jazyků pomocí logických metod
Annotation in Czech
Programování s omezujícími podmínkami tvoří společný rámec a užitečné paradigma pro modelování a řešení kombinatorických úloh z širokého spektra praktických aplikací. Nedávno došlo k rapidnímu rozvoji našeho chápání složitostní krajiny constraintových jazyků, vyvolanému vylepšeními strukturální teorie v souvislosti s potvrzením hypotézy o dichotomii CSP a s vývojem algebraického přístupu k problému Promise CSP. Základním nástrojem jsou standardizované redukce založené na primitivní pozitivní (pp-) definovatelnosti a jejích zobecněních, použité ke zkoumání struktury množin řešení. Navrhovaný projekt má za cíl rozvinout state-of-art metody založené na inspekci struktury těchto redukcí založených na pp-definovatelnosti, a aplikovat je k řešení důležitých otevřených problémů ve třech oblastech: few subpowers a naučitelnost a evaluovatelnost množin řešení, řešitelnost v nedeterministickém logspace pomocí Lineárního Datalogu, a pokrok směrem k úplné klasifikaci constraintových jazyků a PCSP šablon modulo pp-konstruovatelnost.
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - secondary branch
—
OECD FORD - another secondary branch
—
CEP - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
AF - Documentation, librarianship, work with information<br>BC - Theory and management systems<br>BD - Information theory<br>IN - Informatics
Solution timeline
Realization period - beginning
Jan 1, 2025
Realization period - end
Dec 31, 2027
Project status
Z - Beginning multi-year project
Latest support payment
—
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
CEP25-GA0-GA-R
Data delivery date
Feb 27, 2025
Finance
Total approved costs
6,185 thou. CZK
Public financial support
5,892 thou. CZK
Other public sources
293 thou. CZK
Non public and foreign sources
0 thou. CZK