Recent zbMATH articles in MSC 08https://zbmath.org/atom/cc/082023-03-23T18:28:47.107421ZWerkzeugDismantlability, connectedness, and mixing in relational structureshttps://zbmath.org/1503.080012023-03-23T18:28:47.107421Z"Briceño, Raimundo"https://zbmath.org/authors/?q=ai:briceno.raimundo"Bulatov, Andrei A."https://zbmath.org/authors/?q=ai:bulatov.andrei-a"Dalmau, Víctor"https://zbmath.org/authors/?q=ai:dalmau.victor"Larose, Benoît"https://zbmath.org/authors/?q=ai:larose.benoitSummary: The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, statistical physics, and elsewhere. Its structural and algorithmic properties have demonstrated to play a crucial role in many of those applications. For instance, topological properties of the solution set such as connectedness is related to the hardness of CSPs over random structures. In approximate counting and statistical physics, where CSPs emerge in the form of spin systems, mixing properties and the uniqueness of Gibbs measures have been heavily exploited for approximating partition functions or the free energy of spin systems. Additionally, in the decision CSPs, structural properties of the relational structures involved -- like, for example, dismantlability -- and their logical characterizations have been instrumental for determining the complexity and other properties of the problem.
In spite of the great diversity of those features, there are some eerie similarities between them. These were observed and made more precise in the case of graph homomorphisms by \textit{G. R. Brightwell} and \textit{P. Winkler} [J. Comb. Theory, Ser. B 78, No. 1, 141--166 (2000; Zbl 1030.05101)], who showed that the structural property of dismantlability of the target graph, the connectedness of the set of homomorphisms, good mixing properties of the corresponding spin system, and the uniqueness of Gibbs measure are all equivalent. In this paper we go a step further and demonstrate similar connections for arbitrary CSPs. This requires much deeper understanding of dismantling and the structure of the solution space in the case of relational structures, and new refined concepts of mixing introduced by the first author [Ergodic Theory Dyn. Syst. 38, No. 5, 1658--1696 (2016; Zbl 1398.37021)]. In addition, we develop properties related to the study of valid extensions of a given partially defined homomorphism, an approach that turns out to be novel even in the graph case. We also add to the mix the combinatorial property of finite duality and its logic counterpart, FO-definability, studied by \textit{B. Larose} et al. [Log. Methods Comput. Sci. 3, No. 4, Paper 6, 22 p. (2007; Zbl 1131.68098)].
For the entire collection see [Zbl 1414.68003].Dismantlability, connectedness, and mixing in relational structureshttps://zbmath.org/1503.080022023-03-23T18:28:47.107421Z"Briceño, Raimundo"https://zbmath.org/authors/?q=ai:briceno.raimundo"Bulatov, Andrei"https://zbmath.org/authors/?q=ai:bulatov.andrei-a"Dalmau, Víctor"https://zbmath.org/authors/?q=ai:dalmau.victor"Larose, Benoît"https://zbmath.org/authors/?q=ai:larose.benoitSummary: The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, and elsewhere. Its structural and algorithmic properties have been shown to play a crucial role in many of those applications. For instance, in the decision CSPs, structural properties of the relational structures involved -- like, for example, dismantlability -- and their logical characterizations have been instrumental for determining the complexity and other properties of the problem. Topological properties of the solution set such as connectedness are related to the hardness of CSPs over random structures. Additionally, in approximate counting and statistical physics, where CSPs emerge in the form of spin systems, mixing properties and the uniqueness of Gibbs measures have been heavily exploited for approximating partition functions and free energy.
In spite of the great diversity of those features, there are some eerie similarities between them. These were observed and made more precise in the case of graph homomorphisms by \textit{G. R. Brightwell} and \textit{P. Winkler} [J. Comb. Theory, Ser. B 78, No. 1, 141--166 (2000; Zbl 1030.05101)], who showed that dismantlability of the target graph, connectedness of the set of homomorphisms, and good mixing properties of the corresponding spin system are all equivalent. In this paper we go a step further and demonstrate similar connections for arbitrary CSPs. This requires much deeper understanding of dismantling and the structure of the solution space in the case of relational structures, and new refined concepts of mixing introduced by the first author [Ergodic Theory Dyn. Syst. 38, No. 5, 1658--1696 (2016; Zbl 1398.37021)]. In addition, we develop properties related to the study of valid extensions of a given partially defined homomorphism, an approach that turns out to be novel even in the graph case. We also add to the mix the combinatorial property of finite duality and its logic counterpart, FO-definability, studied by \textit{B. Larose} et al. [Log. Methods Comput. Sci. 3, No. 4, Paper 6, 22 p. (2007; Zbl 1131.68098)].Seven lectures on universal algebraic geometryhttps://zbmath.org/1503.080032023-03-23T18:28:47.107421Z"Plotkin, Boris"https://zbmath.org/authors/?q=ai:plotkin.borisFor the entire collection see [Zbl 1415.16003].Relations of some special generalized varietieshttps://zbmath.org/1503.200172023-03-23T18:28:47.107421Z"Tang, Shan Gui"https://zbmath.org/authors/?q=ai:tang.shangui(no abstract)Truth-preservation under fuzzy pp-formulashttps://zbmath.org/1503.680772023-03-23T18:28:47.107421Z"Dellunde, Pilar"https://zbmath.org/authors/?q=ai:dellunde.pilar"Vidal, Amanda"https://zbmath.org/authors/?q=ai:vidal.amandaSummary: How can non-classical logic contribute to the analysis of complexity in computer science? In this paper, we give a step towards this question, taking a logical model-theoretic approach to the analysis of complexity in fuzzy constraint satisfaction. We study fuzzy positive-primitive sentences, and we present an algebraic characterization of classes axiomatized by this kind of sentences in terms of homomorphisms and direct products. The ultimate goal is to study the expressiveness and reasoning mechanisms of non-classical languages, with respect to constraint satisfaction problems and, in general, in modelling decision scenarios.