Dualities in full homomorphisms

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F09%3A00206371" target="_blank" >RIV/00216208:11320/09:00206371 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/10:10081043

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Dualities in full homomorphisms

Popis výsledku v původním jazyce

The Constraint Satisfaction Problem (CSP) is studied for constraints given as requirements in full graph homomorphisms. It is proved that for every finite (full) system of constraints there exists a finite duality, that is, a finite system of prohibitedsources, or subobjects, equivalent with the constraint task. The converse, however does not hold, in fact it is, rather, rare - it is a phenomenon of the Ramsey type. As an illustration we present a number of concrete finite dualities, and of the associated Ramsey phenomena.

Název v anglickém jazyce

Dualities in full homomorphisms

Popis výsledku anglicky

The Constraint Satisfaction Problem (CSP) is studied for constraints given as requirements in full graph homomorphisms. It is proved that for every finite (full) system of constraints there exists a finite duality, that is, a finite system of prohibitedsources, or subobjects, equivalent with the constraint task. The converse, however does not hold, in fact it is, rather, rare - it is a phenomenon of the Ramsey type. As an illustration we present a number of concrete finite dualities, and of the associated Ramsey phenomena.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2010

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

European Journal of Combinatorics

ISSN

0195-6698

e-ISSN

—

Svazek periodika

31

Číslo periodika v rámci svazku

31

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

124

Strana od-do

—

Kód UT WoS článku

000271971000011

EID výsledku v databázi Scopus

—