Дисертації з теми "Monoidal structures"

Le but de cette thèse est de fournir une construction explicite d'une résolution cofibrante des opérades de Balteanu-Fiedorowicz-Schwänzl-Vogt M_n, qui régissent les catégories monoidales itérées.Dans une première partie de la thèse, nous examinons en détail la définition des structures monoïdales dans les 2-catégories, ainsi que la définition des opérades dans les 2-catégories monoïdales, en prenant la 2-catégorie des catégories comme exemple principal. Ensuite, nous démontrons que la catégorie des opérades dans la catégorie des petites catégories hérite d'une structure de modèle par transfert de la structure de modèle folk sur la catégorie des petites catégories. Nous introduisons une notion de présentation polygraphique des opérades dans la catégorie des petites catégories afin de définir des opérades en terme de générateurs et relations à la fois dans la direction opératique et dans la direction catégorique au niveau des morphismes. Nous réexaminons la définition des opérades M_n en termes de présentations polygraphiques, et nous donnons une présentation de l'opérade M_1^infinity qui fournit une résolution cofibrante de l'opérade M_1 dans la structure de modèle folk. Enfin, nous étudions une généralisation du produit tensoriel de Boardman-Vogt dans le contexte des opérades dans la catégorie des catégories. Nous utilisons cette construction pour fournir une résolution cofibrante M_n^infinity de l'opérade M_n à partir de la résolution M_1^infinity de M_1, et ainsi répondre à la question initiale de la thèse
The goal of this thesis is to give an effective construction of a cofibrant resolution of the Balteanu-Fiedorowicz-Schwänzl-Vogt operads M_n, which govern iterated monoidal categories.In a first part of the thesis, we study thoroughly the definition of monoidal structures in 2-categories, and the definition of operads in monoidal 2-categories, with the 2-category of categories as a main motivating example. Then we prove that the category of operads in the category of small categories inherits a model structure by transfer of the folk model structure on the category of small categories. We introduce a notion of polygraphic presentation of operads in the category of small categories in order to define operads with generators and relations in both the operadic direction and the categorical direction at the morphism level. We revisit the definition of the operads M_n in terms of polygraphic presentations, and we gives a presentation of an operad M_1^infinity that provides a cofibrant resolution of the operad M_1 in the folk modelstructure. Eventually, we study a generalization of the Boardman-Vogt tensor product in the context of operads in the category of small categories. We use this construction to provide a cofibrant resolution M_n^infinity of the operad M_n from the resolution M_1^infinity of M_1, and hence, to address the initial question of the thesis

Quantum information brings together theories of physics and computer science. This synthesis challenges the basic intuitions of both fields. In this thesis, we show that adopting a unified and general language for process theories advances foundations and practical applications of quantum information. Our first set of results analyze quantum algorithms with a process theoretic structure. We contribute new constructions of the Fourier transform and Pontryagin duality in dagger symmetric monoidal categories. We then use this setting to study generalized unitary oracles and give a new quantum blackbox algorithm for the identification of group homomorphisms, solving the GROUPHOMID problem. In the remaining section, we construct a novel model of quantum blackbox algorithms in non-deterministic classical computation. Our second set of results concerns quantum foundations. We complete work begun by Coecke et al., definitively connecting the Mermin non-locality of a process theory with a simple algebraic condition on that theory's phase groups. This result allows us to offer new experimental tests for Mermin non-locality and new protocols for quantum secret sharing. In our final chapter, we exploit the shared process theoretic structure of quantum information and distributional compositional linguistics. We propose a quantum algorithm adapted from Weibe et al. to classify sentences by meaning. The clarity of the process theoretic setting allows us to recover a speedup that is lost in the naive application of the algorithm. The main mathematical tools used in this thesis are group theory (esp. Fourier theory on finite groups), monoidal category theory, and categorical algebra.

This thesis is divided into two parts. The first part is concerned with the commutative algebra of certain combinatorial structures arising from uniform hypergraphs. The main focus lies on two particular classes of hypergraphs called chordal hypergraphs and complete hypergraphs, respectively. Both these classes arise naturally as generalizations of the corresponding well known classes of simple graphs. The classes of chordal and complete hypergraphs are introduced and studied in Chapter 2 and Chapter 3 respectively. Chapter 4, that is the content of \cite{E5}, answers a question posed at the P.R.A.G.MAT.I.C. summer school held in Catania, Italy, in 2008. In Chapter 5 we study hypergraph analogues of line graphs and cycle graphs. Chapter 6 is concerned with a connectedness notion for hypergraphs and in Chapter 7 we study a weak version of shellability.The second part is concerned with affine monoids and their monoid rings. Chapter 8 provide a combinatorial study of a class of positive affine monoids that behaves in some sense like numerical monoids. Chapter 9 is devoted to the class of numerical monoids of maximal embedding dimension. A combinatorial description of the graded Betti numbers of the corresponding monoid rings in terms of the minimal generators of the monoids is provided. Chapter 10 is concerned with monomial subrings generated by edge sets of complete hypergraphs.

La combinatoire algébrique est le champ de recherche qui utilise des méthodes combinatoires et des algorithmes pour étudier les problèmes algébriques, et applique ensuite des outils algébriques à ces problèmes combinatoires. L’un des thèmes centraux de la combinatoire algébrique est l’étude des permutations car elles peuvent être interprétées de bien des manières (en tant que bijections, matrices de permutations, mais aussi mots sur des entiers, ordre totaux sur des entiers, sommets du permutaèdre…). Cette riche diversité de perspectives conduit alors aux généralisations suivantes du groupe symétrique. Sur le plan géométrique, le groupe symétrique engendré par les transpositions élémentaires est l’exemple canonique des groupes de réflexions finis, également appelés groupes de Coxeter. Sur le plan monoïdal, ces même transpositions élémentaires deviennent les opérateurs du tri par bulles et engendrent le monoïde de 0-Hecke, dont l’algèbre est la spécialisation à q=0 de la q-déformation du groupe symétrique introduite par Iwahori. Cette thèse se consacre à deux autres généralisations des permutations. Dans la première partie de cette thèse, nous nous concentrons sur les matrices de permutations partielles, en d’autres termes les placements de tours ne s’attaquant pas deux à deux sur un échiquier carré. Ces placements de tours engendrent le monoïde de placements de tours, une généralisation du groupe symétrique. Dans cette thèse nous introduisons et étudions le 0-monoïde de placements de tours comme une généralisation du monoïde de 0-Hecke. Son algèbre est la dégénérescence à q=0 de la q-déformation du monoïde de placements de tours introduite par Solomon. On étudie par la suite les propriétés monoïdales fondamentales du 0-monoïde de placements de tours (ordres de Green, propriété de treillis du R-ordre, J-trivialité) ce qui nous permet de décrire sa théorie des représentations (modules simples et projectifs, projectivité sur le monoïde de 0-Hecke, restriction et induction le long d’une fonction d’inclusion).Les monoïdes de placements de tours sont en fait l’instance en type A de la famille des monoïdes de Renner, définis comme les complétés des groupes de Weyl (c’est-à-dire les groupes de Coxeter cristallographiques) pour la topologie de Zariski. Dès lors, dans la seconde partie de la thèse nous étendons nos résultats du type A afin de définir les monoïdes de 0-Renner en type B et D et d’en donner une présentation. Ceci nous conduit également à une présentation des monoïdes de Renner en type B et D, corrigeant ainsi une présentation erronée se trouvant dans la littérature depuis une dizaine d’années. Par la suite, nous étudions comme en type A les propriétés monoïdales de ces nouveaux monoïdes de 0-Renner de type B et D : ils restent J-triviaux, mais leur R-ordre n’est plus un treillis. Cela ne nous empêche pas d’étudier leur théorie des représentations, ainsi que la restriction des modules projectifs sur le monoïde de 0-Hecke qui leur est associé. Enfin, la dernière partie de la thèse traite de différentes généralisations des permutations. Dans une récente séries d’articles, Châtel, Pilaud et Pons revisitent la combinatoire algébrique des permutations (ordre faible, algèbre de Hopf de Malvenuto-Reutenauer) en terme de combinatoire sur les ordres partiels sur les entiers. Cette perspective englobe également la combinatoire des quotients de l’ordre faible tels les arbres binaires, les séquences binaires, et de façon plus générale les récents permutarbres de Pilaud et Pons. Nous généralisons alors l’ordre faibles aux éléments des groupes de Weyl. Ceci nous conduit à décrire un ordre sur les sommets des permutaèdres, associaèdres généralisés et cubes dans le même cadre unifié. Ces résultats se basent sur de subtiles propriétés des sommes de racines dans les groupes de Weyl qui s’avèrent ne pas fonctionner pour les groupes de Coxeter qui ne sont pas cristallographiques
Algebraic combinatorics is the research field that uses combinatorial methods and algorithms to study algebraic computation, and applies algebraic tools to combinatorial problems. One of the central topics of algebraic combinatorics is the study of permutations, interpreted in many different ways (as bijections, permutation matrices, words over integers, total orders on integers, vertices of the permutahedron…). This rich diversity of perspectives leads to the following generalizations of the symmetric group. On the geometric side, the symmetric group generated by simple transpositions is the canonical example of finite reflection groups, also called Coxeter groups. On the monoidal side, the simple transpositions become bubble sort operators that generate the 0-Hecke monoid, whose algebra is the specialization at q=0 of Iwahori’s q-deformation of the symmetric group. This thesis deals with two further generalizations of permutations. In the first part of this thesis, we first focus on partial permutations matrices, that is placements of pairwise non attacking rooks on a n by n chessboard, simply called rooks. Rooks generate the rook monoid, a generalization of the symmetric group. In this thesis we introduce and study the 0-Rook monoid, a generalization of the 0-Hecke monoid. Its algebra is a proper degeneracy at q = 0 of the q-deformed rook monoid of Solomon. We study fundamental monoidal properties of the 0-rook monoid (Green orders, lattice property of the R-order, J-triviality) which allow us to describe its representation theory (simple and projective modules, projectivity on the 0-Hecke monoid, restriction and induction along an inclusion map).Rook monoids are actually type A instances of the family of Renner monoids, which are completions of the Weyl groups (crystallographic Coxeter groups) for Zariski’s topology. In the second part of this thesis we extend our type A results to define and give a presentation of 0-Renner monoids in type B and D. This also leads to a presentation of the Renner monoids of type B and D, correcting a misleading presentation that appeared earlier in the litterature. As in type A we study the monoidal properties of the 0-Renner monoids of type B and D : they are still J-trivial but their R-order are not lattices anymore. We study nonetheless their representation theory and the restriction of projective modules over the corresponding 0-Hecke monoids. The third part of this thesis deals with different generalizations of permutations. In a recent series of papers, Châtel, Pilaud and Pons revisit the algebraic combinatorics of permutations (weak order, Malvenuto-Reutenauer Hopf algebra) in terms of the combinatorics of integer posets. This perspective encompasses as well the combinatorics of quotients of the weak order such as binary trees, binary sequences, and more generally the recent permutrees of Pilaud and Pons. We generalize the weak order on the elements of the Weyl groups. This enables us to describe the order on vertices of the permutahedra, generalized associahedra and cubes in the same unified context. These results are based on subtle properties of sums of roots in Weyl groups, and actually fail for non-crystallographic Coxeter groups

Dans la première moitié de ce mémoire, nous étudions les invariants polynomiaux définis par Aguiar et Ardila dans arXiv:1709.07504 dans le contexte des monoïdes de Hopf. Nous donnons d'abord une interprétation combinatoire de ces polynômes pour les monoïdes de Hopf des permutaèdres généralisés et des hypergraphes,sur les entiers naturels et négatifs. Nous en déduisons ensuite des interprétations similaires sur d'autres objets combinatoires(graphes, complexes simpliciaux, building sets, etc).Dans la seconde moitié de ce mémoire, nous proposons une nouvelle façon de définir et d'étudier des opérades de multigraphes et d'objets similaires.Nous étudions en particulier deux opérades obtenues avec cette méthode. La première est une généralisation directe de l'opérade Kontsevich-Willwacher,qui peut être considérée comme une opérade canonique sur les multigraphes et possède de nombreuses sous-opérades intéressantes.La seconde est une extension naturelle de l'opérade pré-Lie et a aussi un lien avec l'opérade précédente.Nous présentons également divers résultats sur certaines sous-opérades finiment enegendrées et établissons des liens entre elles et les opérades commutative et commutative magmatique
In the first half of this dissertation, we study the polynomial invariants defined by Aguiar and Ardila in arXiv:1709.07504 in the context of Hopf monoids. We first give a combinatorial interpretation of these polynomials over the Hopf monoids of generalized permutahedra and hypergraphs in both non negative and negative integers. We then use them to deduce similar interpretation on other combinatorial objects(graphs, simplicial complexes, building sets, etc).In the second half of this disseration, we propose a new way of defining and studying operads on multigraphs and similar objects.We study in particular two operads obtained with our method. The former is a direct generalization of the Kontsevich-Willwacher operad.This operad can be seen as a canonical operad on multigraphs,and has many interesting suboperads.The latter operad is a natural extension of the pre-Lie operad in a sense developed here and it is related to the multigraph operad. We also present various results on some of the finitely generated suboperads of the multigraph operad and establish links between them and the commutative operad and the commutative magmatic operad

Ce travail porte sur les propriétés algébriques des groupes de tresses d'Artin et des systèmes autodistributifs à gauche, des objets intimement liés. La première partie est une analyse syntaxique de la forme normale de Bressaud pour les tresses. Le principal résultat est une traduction en termes de systèmes de réécriture de l'existence de la forme normale, initialement établie par des méthodes géométriques. La seconde partie est centrée sur la conjecture de plongement pour l'autodistributivité, un des énoncés ouverts principaux du domaine. On discute les multiples approches (y compris calculatoires) pouvant mener à cette conjecture, et on établit des résultats positifs partiels
In this work, we investigate algebraic properties for Artin's braid groups and self-distributive systems on the left, two objets which are linked. The first part is a syntactic analysis of Bressaud's normal formal for braids. The principal result is a translation in terms of rewriting systems of the existence of Bressaud's normal form, initially established by geometric methods. The second part deals with the embedding conjecture for self-distributivity, one of the principal open statements of the field. We discuss the various ways (including the computing ones) which could lead to this conjecture, and we establish some partial positive results

In this thesis local methods are made available as a tool to study theunary parts of clones (or, equivalently, the weak Krasner algebras). Using thelanguage of model theory and Galois connections we develop a link betweenhomomorphism-homogeneous relational structures and local methods, via thenotion of endolocality. The theoretical results that are obtained are used to developa systematic theory for the classification of homomorphism-homogeneousrelational structures.
U ovoj tezi su razvijene lokalne metode koje se mogu koristiti za izu-ˇcavanje unarnih delova klonova (ili, ekvivalentno, slabih Krasnerovih algebri).Koriˇs´cenjem jezika teorije modela i Galoovih veza uspostavljen je odnos izmeduhomomorfizam-homogenih relacionih struktura i lokalnih metoda, preko pojmaendolokalnosti. Dobijeni teoretski rezultati su upotrebljeni za razvoj sistematsketeorije za klasifikaciju homomorfizam-homogenih struktura.

Let Ω be the Fraïssé limit of a class of relational structures. We seek to answer the following semigroup theoretic question about Ω. What are the group H-classes, i.e. the maximal subgroups, of End(Ω)? Fraïssé limits for which we answer this question include the random graph R, the random directed graph D, the random tournament T, the random bipartite graph B, Henson's graphs G[subscript n] (for n greater or equal to 3) and the total order Q. The maximal subgroups of End(Ω) are closely connected to the automorphism groups of the relational structures induced by the images of idempotents from End(Ω). It has been shown that the relational structure induced by the image of an idempotent from End(Ω) is algebraically closed. Accordingly, we investigate which groups can be realised as the automorphism group of an algebraically closed relational structure in order to determine the maximal subgroups of End(Ω) in each case. In particular, we show that if Γ is a countable graph and Ω = R,D,B, then there exist 2[superscript aleph-naught] maximal subgroups of End(Ω) which are isomorphic to Aut(Γ). Additionally, we provide a complete description of the subsets of Q which are the image of an idempotent from End(Q). We call these subsets retracts of Q and show that if Ω is a total order and f is an embedding of Ω into Q such that im f is a retract of Q, then there exist 2[superscript aleph-naught] maximal subgroups of End(Q) isomorphic to Aut(Ω). We also show that any countable maximal subgroup of End(Q) must be isomorphic to Zⁿ for some natural number n. As a consequence of the methods developed, we are also able to show that when Ω = R,D,B,Q there exist 2[superscript aleph-naught] regular D-classes of End(Ω) and when Ω = R,D,B there exist 2[superscript aleph-naught] J-classes of End(Ω). Additionally we show that if Ω = R,D then all regular D-classes contain 2[superscript aleph-naught] group H-classes. On the other hand, we show that when Ω = B,Q there exist regular D-classes which contain countably many group H-classes.

Dependent type theories are a kind of mathematical foundations investigated both for the formalisation of mathematics and for reasoning about programs. They are implemented as the kernel of many proof assistants and programming languages with proofs (Coq, Agda, Idris, Dedukti, Matita, etc). Dependent types allow to encode elegantly and constructively the universal and existential quantifications of higher-order logics and are therefore adapted for writing logical propositions and proofs. However, their usage is not limited to the area of pure logic. Indeed, some recent work has shown that they can also be powerful for driving the construction of programs. Using more precise types not only helps to gain confidence about the program built, but it can also help its construction, giving rise to a new style of programming called Type-Driven Development. However, one difficulty with reasoning and programming with dependent types is that proof obligations arise naturally once programs become even moderately sized. For example, implementing an adder for binary numbers indexed over their natural number equivalents naturally leads to proof obligations for equalities of expressions over natural numbers. The need for these equality proofs comes, in intensional type theories (like CIC and ML) from the fact that in a non-empty context, the propositional equality allows us to prove as equal (with the induction principles) terms that are not judgementally equal, which implies that the typechecker can't always obtain equality proofs by reduction. As far as possible, we would like to solve such proof obligations automatically, and we absolutely need it if we want dependent types to be use more broadly, and perhaps one day to become the standard in functional programming. In this thesis, we show one way to automate these proofs by reflection in the dependently typed programming language Idris. However, the method that we follow is independent from the language being used, and this work could be reproduced in any dependently-typed language. We present an original type-safe reflection mechanism, where reflected terms are indexed by the original Idris expression that they represent, and show how it allows us to easily construct and manipulate proofs. We build a hierarchy of correct-by-construction tactics for proving equivalences in semi-groups, monoids, commutative monoids, groups, commutative groups, semi-rings and rings. We also show how each tactic reuses those from simpler structures, thus avoiding duplication of code and proofs. Finally, and as a conclusion, we discuss the trust we can have in such machine-checked proofs.

Thèse par articles.
La présente thèse fait état des avancées en logique déontique et propose des outils formels pertinents à l'analyse de la validité des inférences légales. D'emblée, la logique vise l'abstraction de différentes structures. Lorsqu'appliquée en argumentation, la logique permet de déterminer les conditions de validité des inférences, fournissant ainsi un critère afin de distinguer entre les bons et les mauvais raisonnements. Comme le montre la multitude de paradoxes en logique déontique, la modélisation des inférences normatives fait cependant face à divers problèmes. D'un point de vue historique, ces difficultés ont donné lieu à différents courants au sein de la littérature, dont les plus importants à ce jour sont ceux qui traitent de l'action et ceux qui visent la modélisation des obligations conditionnelles. La présente thèse de doctorat, qui a été rédigée par articles, vise le développement d'outils formels pertinents à l'analyse du discours juridique. En première partie, nous proposons une revue de la littérature complémentaire à ce qui a été entamé dans Peterson (2011). La seconde partie comprend la contribution théorique proposée. Dans un premier temps, il s'agit d'introduire une logique déontique alternative au système standard. Sans prétendre aller au-delà de ses limites, le système standard de logique déontique possède plusieurs lacunes. La première contribution de cette thèse est d'offrir un système comparable répondant au différentes objections pouvant être formulées contre ce dernier. Cela fait l'objet de deux articles, dont le premier introduit le formalisme nécessaire et le second vulgarise les résultats et les adapte aux fins de l'étude des raisonnements normatifs. En second lieu, les différents problèmes auxquels la logique déontique fait face sont abordés selon la perspective de la théorie des catégories. En analysant la syntaxe des différents systèmes à l'aide des catégories monoïdales, il est possible de lier certains de ces problèmes avec des propriétés structurelles spécifiques des logiques utilisées. Ainsi, une lecture catégorique de la logique déontique permet de motiver l'introduction d'une nouvelle approche syntaxique, définie dans le cadre des catégories monoïdales, de façon à pallier les problèmes relatifs à la modélisation des inférences normatives. En plus de proposer une analyse des différentes logiques de l'action selon la théorie des catégories, la présente thèse étudie les problèmes relatifs aux inférences normatives conditionnelles et propose un système déductif typé.
The present thesis develops formal tools relevant to the analysis of legal discourse. When applied to legal reasoning, logic can be used to model the structure of legal inferences and, as such, it provides a criterion to discriminate between good and bad reasonings. But using logic to model normative reasoning comes with some problems, as shown by the various paradoxes one finds within the literature. From a historical point of view, these paradoxes lead to the introduction of different approaches, such as the ones that emphasize the notion of action and those that try to model conditional normative reasoning. In the first part of this thesis, we provide a review of the literature, which is complementary to the one we did in Peterson (2011). The second part of the thesis concerns our theoretical contribution. First, we propose a monadic deontic logic as an alternative to the standard system, answering many objections that can be made against it. This system is then adapted to model unconditional normative inferences and test their validity. Second, we propose to look at deontic logic from the proof-theoretical perspective of category theory. We begin by proposing a categorical analysis of action logics and then we show that many problems that arise when trying to model conditional normative reasoning come from the structural properties of the logic we use. As such, we show that modeling normative reasoning within the framework of monoidal categories enables us to answer many objections in favour of dyadic and non-monotonic foundations for deontic logic. Finally, we propose a proper typed deontic system to model legal inferences.