Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Non-homogenizable classes of finite structures

Autor
Atserias, A.; Torunczyk, S.
Tipus d'activitat
Presentació treball a congrés
Nom de l'edició
25th EACSL Annual Conference on Computer Science Logic
Any de l'edició
2016
Data de presentació
2016-08-29
Llibre d'actes
25th EACSL Annual Conference on Computer Science Logic (CSL 2016)
Pàgina inicial
1
Pàgina final
16
Editor
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
DOI
10.4230/LIPIcs.CSL.2016.16
Projecte finançador
A unified theory of algorithmic relaxations
Repositori
http://drops.dagstuhl.de/opus/volltexte/2016/6556/ Obrir en finestra nova
http://hdl.handle.net/2117/100189 Obrir en finestra nova
Resum
Homogenization is a powerful way of taming a class of finite structures with several interesting applications in different areas, from Ramsey theory in combinatorics to constraint satisfaction problems (CSPs) in computer science, through (finite) model theory. A few sufficient conditions for a class of finite structures to allow homogenization are known, and here we provide a necessary condition. This lets us show that certain natural classes are not homogenizable: 1) the class of locally consis...
Citació
Atserias, A., Torunczyk, S. Non-homogenizable classes of finite structures. A: Annual Conference of the European Association for Computer Science Logic. "25th EACSL Annual Conference on Computer Science Logic (CSL 2016)". Marseille: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, p. 16:1-16:16.
Paraules clau
Fraïssé Class, Amalgmation Class, Reduct, Constraint Satisfaction Problem, Bounded Width
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

Arxius