Les problèmes de satisfaction de contraintes, qui consistent à attribuer des valeurs à des variables en respectant un ensemble de contraintes, constituent une large classe de problèmes naturels. Pour étudier la complexité de ces problèmes, il est commode de les voir comme des problèmes d'homomorphismes vers des structures relationnelles. Un axe de recherche actuel est la caractérisation des classes de complexité auxquelles appartient le problème d'homomorphisme, ceci dans la perspective de confirmer des conjectures reliant les propriétés algébriques des structures relationelles à la complexité du problème d'homomorphisme. Cette thèse propose dans un premier temps la caractérisation des digraphes pour lesquels le problème d'homomorphisme avec listes appartient à FO. On montre également que dans le cas du problèmes d'homomorphisme avec listes sur les digraphes télescopiques, les conjectures reliant algèbre et complexité sont confirmées. Dans un deuxième temps, on caractérise les graphes pour lesquels le problème d'homomorphisme avec listes est résoluble par cohérence d'arc. On introduit la notion de polymorphisme monochromatique et on propose un algorithme simple qui résoud le problème d'homomorphisme avec listes si le graphe cible admet un polymorphisme monochromatique TSI d'arité k pour tout k ≥ 2. / Constraint satisfaction problems, consisting in assigning values to variables while respecting a set of constraints, form a large class of natural problems. In order to study the complexity of these problems, it is convenient to see them as homomorphism problems on relational structures. One current research topic is to characterise complexity classes where the homomorphism problem belongs. The ultimate goal is to confirm conjectures that bind together algebraic properties of the relationnal structure and complexity of the homomorphism problem. At first, the thesis characterizes digraphs which generate FO list-homomorphism problems. It is shown that in the particular case of telescopic digraphs, conjectures binding together algebra and complexity are confirmed. Subsequently, we characterize graphs which generate arc-consistency solvable list-homomorphism problems. We introduce the notion of monochromatic polymorphism and we propose a simple algorithm which solves the list-homomorphism problem if the target graph admits a monochromatic TSI polymorphism of arity k for every k ≥ 2.

We define a variation of injective oriented colouring as reflexive injective oriented colouring, or rio-colouring for short, which requires an oriented colouring to be injective on the neighbourhoods of the underlying graph, without requiring the colouring to be proper. An analysis of the complexity of the problem of deciding whether an oriented graph has a k-rio-colouring is considered, and we find a dichotomy for the values of k below 3 and above, being in P or NP-complete, respectively. Characterizations are given for the oriented graphs resulting from the polynomial-time solvable cases, and bounds are given for the rio-chromatic number in terms of maximum in-degree and out-degree, in general, and for oriented trees. Also, a polynomial-time algorithm is developed to aid in the rio-colouring of oriented trees.

This work analyses properties of relational structures that imply a high degree of symmetry. A structure is called homogeneous if every mapping from any finite substructure can be extended to a mapping over the whole structure. The various types of these mappings determine corresponding types of homogeneity. A prominent position belongs to ultrahomogeneity, for which every local isomorphism can be extended to an automorphism. In contrast to graphs, the classification of ultrahomogeneous relational struc- tures is still an open problem. The task of this work is to characterize "the distance" to homogeneity using two approaches. Firstly, the classification of homogeneous structures is studied when the "complexity" of a structure is increased by introducing more relations. This leads to various classifications of homomorphism-homogeneous L-colored graphs for different L, where L- colored graphs are graphs having sets of colors from a partially ordered set L assigned to vertices and edges. Moreover a hierarchy of classes of ho- mogeneous structures defined via types of homogeneity is studied from the viewpoint of classes coincidence. The second approach analyses for fixed classes of structures the least way to extend their language so as to achieve homogeneity. We obtain results about relational complexity for finite...

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-07-23T14:23:04Z No. of bitstreams: 1 RIVALDO DO NASCIMENTO JÚNIOR - DISSERTAÇÃO PPGMAT 2009..pdf: 371424 bytes, checksum: 6e808f19bfcee3712a8cc10f221c042b (MD5) / Made available in DSpace on 2018-07-23T14:23:04Z (GMT). No. of bitstreams: 1 RIVALDO DO NASCIMENTO JÚNIOR - DISSERTAÇÃO PPGMAT 2009..pdf: 371424 bytes, checksum: 6e808f19bfcee3712a8cc10f221c042b (MD5) Previous issue date: 2009-04 / Neste trabalho apresentamos um modelo para a superálgebra das matrizes triangulares superiores e mostraremos como obter o produto de dois T-ideais como núcleo de um homomorfismo de álgebras. em seguida, mostraremos como obter as identidades polinomiais para a álgebra das matrizes triangulares em blocos com Z2-graduação a partir das identidades ordinárias das álgebras de sua diagonal principal. / In this work we present a general model for the superalgebra of upper triangular matrices and show how to obtain the product of two T-ideals as the kernel of a homomorphism between two algebras. Next, we show how to obtain the polynomial identities for algebra of the block-triangular matrices with Z2-grading from the ordinary identities of the algebras of its main diagonal.

Orientador: Antonio Aparecido de Andrade / Banca: Edson Donizete de Carvalho / Banca: Jéfferson Luiz Rocha Bastos / Resumo: Neste trabalho é feito um estudo sobre famílias de reticulados algébricos e reticulados ideais. Nosso principal objetivo é a construção de reticulados que são versões rotacioanadas de reticulados já conhecidos na literatura. Deste modo, apresentamos construções obtidas via polinômios, via perturbações do homomorfismo canônico e, também, construções ciclotômicas a partir fo reticulado Zn. / Abstract: This work presents a study of algebraic and families of ideal lattices. Our main goal is the construction of lattices which are rotated versions of known lattices in the literature. In this way, we present constructions obtained via polynomials, via pertubations of the canonical homomorphism, and also cyclotomic construction from the lattice Zn. / Mestre

Made available in DSpace on 2015-03-03T15:48:40Z (GMT). No. of bitstreams: 1 IvanM_TESE.pdf: 1798098 bytes, checksum: 03ae24b47cf77f2591da995af74bd268 (MD5) Previous issue date: 2013-12-06 / In the literature there are several proposals of fuzzi cation of lattices and ideals concepts. Chon in (Korean J. Math 17 (2009), No. 4, 361-374), using the notion of fuzzy order relation de ned by Zadeh, introduced a new notion of fuzzy lattice and studied the level sets of fuzzy lattices, but did not de ne a notion of fuzzy ideals for this type of fuzzy lattice. In this thesis, using the fuzzy lattices de ned by Chon, we de ne fuzzy homomorphism between fuzzy lattices, the operations of product, collapsed sum, lifting, opposite, interval and intuitionistic on bounded fuzzy lattices. They are conceived as extensions of their analogous operations on the classical theory by using this de nition of fuzzy lattices and introduce new results from these operators. In addition, we de ne ideals and lters of fuzzy lattices and concepts in the same way as in their characterization in terms of level and support sets. One of the results found here is the connection among ideals, supports and level sets. The reader will also nd the de nition of some kinds of ideals and lters as well as some results with respect to the intersection among their families. Moreover, we introduce a new notion of fuzzy ideals and fuzzy lters for fuzzy lattices de ned by Chon. We de ne types of fuzzy ideals and fuzzy lters that generalize usual types of ideals and lters of lattices, such as principal ideals, proper ideals, prime ideals and maximal ideals. The main idea is verifying that analogous properties in the classical theory on lattices are maintained in this new theory of fuzzy ideals. We also de ne, a fuzzy homomorphism h from fuzzy lattices L and M and prove some results involving fuzzy homomorphism and fuzzy ideals as if h is a fuzzy monomorphism and the fuzzy image of a fuzzy set ~h(I) is a fuzzy ideal, then I is a fuzzy ideal. Similarly, we prove for proper, prime and maximal fuzzy ideals. Finally, we prove that h is a fuzzy homomorphism from fuzzy lattices L into M if the inverse image of all principal fuzzy ideals of M is a fuzzy ideal of L. Lastly, we introduce the notion of -ideals and - lters of fuzzy lattices and characterize it by using its support and its level set. Moreover, we prove some similar properties in the classical theory of - ideals and - lters, such as, the class of -ideals and - lters are closed under intersection. We also de ne fuzzy -ideals of fuzzy lattices, some properties analogous to the classical theory are also proved and characterize a fuzzy -ideal on operation of product between bounded fuzzy lattices L and M and prove some results.

Ce mémoire traite de la construction d’un nouvel invariant des cobordismes lagrangiens. Cette construction est inspirée des travaux récents de Solomon dans lesquels une extension de l’homomorphisme de Calabi aux chemins lagrangiens exacts est donnée. Cette extension fut entre autres motivée par le fait que le graphe d’une isotopie hamiltonienne est un chemin lagrangien exact. Nous utilisons la suspension lagrangienne, qui associe à chaque chemin lagrangien exact un cobordisme lagrangien, pour étendre la construction de Solomon aux cobordismes lagrangiens. Au premier chapitre nous donnons une brève exposition des propriétés élémentaires des variétés symplectiques et des sous-variétés lagrangiennes. Le second chapitre traite du groupe des difféomorphismes hamiltoniens et des propriétés fondamentales de l’homomorphisme de Calabi. Le chapitre 3 est dédié aux chemins lagrangiens, l’invariant de Solomon et ses points critiques. Au dernier chapitre nous introduisons la notion de cobordisme lagrangien et construisons le nouvel invariant pour finalement analyser ses points critiques et l’évaluer sur la trace de la chirurgie de deux courbes sur le tore. Dans le cadre de ce calcul, nous serons en mesure de borner la valeur du nouvel invariant en fonction de l’ombre du cobordisme, une notion récemment introduite par Cornea et Shelukhin. / In this master's thesis, we construct a new invariant of Lagrangian cobordisms. This construction is inspired by the recent works of Solomon in which an extension of the Calabi homomorphism to exact Lagrangian paths is given. Solomon's extension was motivated by the fact that the graph of any Hamiltonian isotopy is an exact Lagrangian path. We use the Lagrangian suspension construction, which associates to every exact Lagrangian path a Lagrangian cobordism, to extend Solomon's invariant to Lagrangian cobordisms. In the first chapter, we give a brief introduction to the elementary properties of symplectic manifolds and their Lagrangian submanifolds. In the second chapter, we present an introduction to the group of Hamiltonian diffeomorphisms and discuss the fundamental properties of the Calabi homomorphism. Chapter 3 is dedicated to Lagrangian paths, Solomon's invariant and its critical points. In the last chapter, we introduce the notion of Lagrangian cobordism and we construct the new invariant. We analyze its critical points and evaluate it on the trace of the Lagrangian surgery of two curves on the torus. In this setting we further bound the new invariant in terms of the shadow of the cobordism, a notion recently introduced by Cornea and Shelukhin.

This Thesis consists of four independent parts. In the first part I prove that the delooping, i.e.the classifying space, of a grouplike monoid is an $H$-space if and only if its multiplication is a homotopy homomorphism. This is an extension and clarification of a result of Sugawara. Furthermore I prove that the Moore loop space functor and the construction of the classifying space induce an adjunction on the corresponding homotopy categories. In the second part I extend a result of G. Dunn, by proving that the tensorproduct $C_{n_1}\otimes\dots \otimes C_{n_j}$ of little cube operads is a topologically equivalent suboperad of $C_{n_1 \dots n_j}$. In the third part I describe operads as algebras over a certain colored operad. By application of results of Boardman and Vogt I describe a model of the homotopy category of topological operads and algebras over them, as well as a notion of lax operads, i.e. operads whose axioms are weakened up to coherent homotopies. Here the W-construction, a functorial cofibrant replacement for a topological operad, plays a central role. As one application I construct a model for the homotopy category of topological categories. C. Berger claimed to have constructed an operad structure on the permutohedras, whose associated monad is exactly the Milgram-construction of the free two-fold loop space. In the fourth part I prove that this statement is not correct.

Basically, the connection of two many-sorted theories is obtained by taking their disjoint union, and then connecting the two parts through connection functions that must behave like homomorphisms on the shared signature. We determine conditions under which decidability of the validity of universal formulae in the component theories transfers to their connection. In addition, we consider variants of the basic connection scheme.

We find an orientation of a tree with 20 vertices such that the corresponding fixed-template constraint satisfaction problem (CSP) is NP-complete, and prove that for every orientation of a tree with fewer vertices the corresponding CSP can be solved in polynomial time. We also compute the smallest tree that is NL-hard (assuming L≠NL), the smallest tree that cannot be solved by arc consistency, and the smallest tree that cannot be solved by Datalog. Our experimental results also support a conjecture of Bulín concerning a question of Hell, Nešetřil and Zhu, namely that ‘easy trees lack the ability to count’. Most proofs are computer-based and make use of the most recent universal-algebraic theory about the complexity of finite-domain CSPs. However, further ideas are required because of the huge number of orientations of trees. In particular, we use the well-known fact that it suffices to study orientations of trees that are cores and show how to efficiently decide whether a given orientation of a tree is a core using the arc-consistency procedure. Moreover, we present a method to generate orientations of trees that are cores that works well in practice. In this way we found interesting examples for the open research problem to classify finite-domain CSPs in NL.