CCL

Összesen 5 találat.
#/oldal:
Részletezés:
Rendezés:

1.

001-es BibID:BIBFORM104107
035-os BibID:(WoS)000483940500003 (Scopus)85072740831
Első szerző:Bodirsky, Manuel
Cím:Constraint Satisfaction Problems for Reducts of Homogeneous Graphs / Manuel Bodirsky, Barnaby Martin, Michael Pinsker, Andras Pongrácz
Dátum:2019
ISSN:0097-5397
Megjegyzések:For n \geq 3, let (Hn, E) denote the nth Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on n vertices. We show that for all structures \Gamma with domain Hn whose relations are first-order definable in (Hn, E) the constraint satisfaction problem for \Gamma either is in P or is NP-complete. We moreover show a similar complexity dichotomy for all structures whose relations are first-order definable in a homogeneous graph whose reflexive closure is an equivalence relation. Together with earlier results, in particular for the random graph, this completes the complexity classification of constraint satisfaction problems of structures first-order definable in countably infinite homogeneous graphs: all such problems are either in P or NP-complete.
Tárgyszavak:Természettudományok Matematika- és számítástudományok idegen nyelvű folyóiratközlemény külföldi lapban
folyóiratcikk
constraint satisfaction problems
homogeneous structures
first-order reducts
universal algebra
structural Ramsey theory
computational complexity
Megjelenés:Siam Journal On Computing. - 48 : 4 (2019), p. 1224-1264. -
További szerzők:Martin, Barnaby Pinsker, Michael Pongrácz András (1986-) (matematikus)
Pályázati támogatás:OTKA-109185
OTKA
EFOP-3.6.2-16-2017-00015
EFOP
FK 124814
Egyéb
PD 125160
Egyéb
Internet cím:Szerző által megadott URL
DOI
Intézményi repozitóriumban (DEA) tárolt változat
Borító:

2.

001-es BibID:BIBFORM083400
Első szerző:Bodirsky, Manuel
Cím:The 42 reducts of the random ordered graph / Manuel Bodirsky, Michael Pinsker, András Pongrácz
Dátum:2015
ISSN:0024-6115
Megjegyzések:The random ordered graph is the up to isomorphism unique countable homogeneous linearly ordered graph that embeds all finite linearly ordered graphs. We determine the reducts of the random ordered graph up to first-order interdefinability.
Tárgyszavak:Természettudományok Matematika- és számítástudományok idegen nyelvű folyóiratközlemény külföldi lapban
folyóiratcikk
Megjelenés:Proceedings of the London Mathematical Society. - 111 : 3 (2015), p. 591-632. -
További szerzők:Pinsker, Michael Pongrácz András (1986-) (matematikus)
Pályázati támogatás:FP7/2007-2013 257039
egyéb
Internet cím:Szerző által megadott URL
DOI
Intézményi repozitóriumban (DEA) tárolt változat
Borító:

3.

001-es BibID:BIBFORM079770
Első szerző:Bodirsky, Manuel
Cím:Reconstructing the topology of clones / Bodirsky Manuel, Pinsker Michael, Pongrácz András
Dátum:2017
ISSN:0002-9947
Megjegyzések:Function clones are sets of functions on a fixed domain that are closed under composition and contain the projections. They carry a natural algebraic structure, provided by the laws of composition which hold in them, as well as a natural topological structure, provided by the topology of pointwise convergence, under which composition of functions becomes continuous. Inspired by recent results indicating the importance of the topological ego of function clones even for originally algebraic problems, we study questions of the following type: In which situations does the algebraic structure of a function clone determine its topological structure? We pay particular attention to function clones which contain an oligomorphic permutation group, and discuss applications of this situation in model theory and theoretical computer science.
Tárgyszavak:Természettudományok Matematika- és számítástudományok idegen nyelvű folyóiratközlemény külföldi lapban
Megjelenés:Transactions Of The American Mathematical Society. - 369 : 5 (2017), p. 3707-3740. -
További szerzők:Pinsker, Michael Pongrácz András (1986-) (matematikus)
Internet cím:Szerző által megadott URL
DOI
Intézményi repozitóriumban (DEA) tárolt változat
Borító:

4.

001-es BibID:BIBFORM078974
035-os BibID:(WoS)000670658100008 (Scopus)85109491413
Első szerző:Bodirsky, Manuel
Cím:Projective Clone Homomorphisms / Manuel Bodirsky, Michael Pinsker, András Pongrácz
Dátum:2021
ISSN:0022-4812
Megjegyzések:It is known that a countable ?-categorical structure interprets all finite structures primitively positively if and only if its polymorphism clone maps to the clone of projections on a two-element set via a continuous clone homomorphism. We investigate the relationship between the existence of a clone homomorphism to the projection clone, and the existence of such a homomorphism which is continuous and thus meets the above criterion.
Tárgyszavak:Természettudományok Matematika- és számítástudományok idegen nyelvű folyóiratközlemény külföldi lapban
folyóiratcikk
Megjelenés:Journal of Symbolic Logic. - 86 : 1 (2021), p. 148-161. -
További szerzők:Pinsker, Michael Pongrácz András (1986-) (matematikus)
Pályázati támogatás:FP7/2007-2013 257039
FP7
Internet cím:Szerző által megadott URL
DOI
Intézményi repozitóriumban (DEA) tárolt változat
Borító:

5.

001-es BibID:BIBFORM078973
Első szerző:Bodirsky, Manuel
Cím:The universal homogeneous binary tree / Manuel Bodirsky, David Bradley-Williams, Michael Pinsker, András Pongrácz
Dátum:2018
ISSN:0955-792X
Tárgyszavak:Természettudományok Matematika- és számítástudományok idegen nyelvű folyóiratközlemény külföldi lapban
Semilinear order
reduct
model companion
model-complete core
permutation group
endomorphism monoid
constraint satisfaction problem
Megjelenés:Journal Of Logic And Computation. - 28 : 1 (2018), p. 133-163. -
További szerzők:Bradley-Williams, David Pinsker, Michael Pongrácz András (1986-) (matematikus)
Pályázati támogatás:FP7/2007-2013 257039
FP7
FP7/2007-2013 238381
FP7
OTKA-109185
OTKA
Internet cím:Szerző által megadott URL
DOI
Intézményi repozitóriumban (DEA) tárolt változat
Borító:
Rekordok letöltése1