Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2011-2012 / Une des questions incontournables qu'on se pose en théorie des langages est de savoir si une logique est décidable. Autrement dit, pour une logique donnée, on veut savoir s'il existe un algorithme qui détermine si un langage donné est exprimable dans cette logique. Depuis les travaux de Schützenberger, McNaughton et Papert sur la logique de premier ordre sur les mots, on reconnait l'importance de la théorie algébrique des langages pour résoudre ces questions de décidabilité. Un autre exemple historique est la caractérisation de Simon des langages testables par morceaux de mots par les monodes J -triviaux. On dit qu'un langage est testable par morceaux si on peut le définir par une combinaison booléenne d'expressions régulieres de la forme [symbol]. Ces langages sont exactement ceux qui sont définis par la clôture booléenne de [symbol] et le théorème de Simon engendre un algorithme qui en resout la décidabilité. Suite aux succès sur les mots, on a attaque les mêmes questions de décidabilité de logiques sur les langages de forêts, plus spéciquement sur les langages d'arbres. Dernièrement, Bojanczyk, Segoufin et Straubing ont pu démontrer un analogue du théorème de Simon pour les forêts. En effet, ils ont pu caractériser la clôture booléenne de [symbol], c'est-à-dire les langages testables par morceaux, en fonction d'une structure algébrique nommée algèbre de forêts. Ce mémoire est d'abord un état de l'art de la théorie algébrique des langages testables par morceaux. Entre autres, nous présentons le théorème de Simon sur les mots en passant par un résultat de Straubing et Thérien qui utilise la théorie des monodes partiellement ordonnés. Ensuite, nous étudions un pendant de ce résultat pour les algèbres de forêts. Finalement, nous règlons la décidabilité des langages de mots bien emboîtés testables par morceaux, une sous-classe des langages visiblement à pile. En efet, nous proposons un algorithme qui utilise le résultat de Bojanczyk, Segoufin et Straubing sur les langages de forêts.

Une tresse est une classe d'équivalence de mots de tresse. Diverses formes normales sur les tresses ont été décrites dans la littérature, c'est-à-dire, divers moyens de sélection, pour toute tresse, d'un mot de tresse distingué la représentant. Définie de façon naturelle sur les monoïdes de tresses de Birman-Ko-Lee (ou duaux), la forme normale tournante peut être étendue au groupe de tresses tout entier. Ici, nous donnons des contraintes de nature combinatoire satisfaites par cette nouvelle forme normale. Nous en obtenons ainsi une caractérisation et montrons que l'ensemble des formes normales tournantes des tresses duales constitue un langage régulier.<br /><br />Un résultat de P. Dehornoy (1992) affirme que toute tresse non triviale admet un représentant sigma-défini. Ce résultat est à la base de la construction de l'ordre des tresses. A l'aide de la forme normale tournante et de ses propriétés, nous montrons que toute tresse admet un représentant sigma-défini de longueur quasi-géodésique, ce qui résout une question ouverte depuis une quinzaine d'années. <br /><br />Un résultat de R. Laver montre que les monoïdes de Birman-Ko-Lee munis de l'ordre des tresses sont bien ordonnés mais laisse ouvert la détermination de leurs longueurs.<br />A l'aide de la forme normale tournante, nous obtenons une caractérisation de l'ordre des tresses sur le monoïde de Birman-ko-Lee à n brins à partir de sa restriction sur celui à (n-1) brins. Une conséquence de ce résultat est une nouvelle démonstration du résultat de R. Laver ainsi que la détermination de la longueur des monoïdes de tresses duaux munis de l'ordre des tresses.

Les tuiles sont des structures finies, linéaires ou arborescentes, possédantune notion de chevauchement. Elles sont utiles en informatique pourreprésenter des objets musicaux, comme étudié par Janin [2016]. Nous étudieronsles ensembles de tuiles, en particulier comme représentations d’objetsalgébriques, en se basant sur la théorie des semigroupes inversifs.Nos principaux objets d’étude seront les langages de tuiles, et les reconnaisseursappropriés, que l’on peut définir en adaptant aux tuiles des notionsbien connues sur les langages de mots. Nous nous intéresserons à la reconnaissancepar automate, en présentant des automates sur les tuiles linéaires etarborescentes. Nous remarquerons les limites de la puissance de tels automates.Tandis que la notion de reconnaissance par morphisme de monoïdes estinadaptée aux langages de tuiles, nous définirons celle de reconnaissabilité parprémorphisme, ou quasi-reconnaissabilité. Nous étudierons les liens entre quasireconnaissabilitéet reconnaissabilité par automate de tuile.Nous explorerons enfin les propriétés de clôtures de l’ensemble de langagesde tuiles reconnus par automate, et de ceux reconnus par prémorphisme. Ladernière partie sera essentiellement consacrée aux tuiles linéaires, et présenterale monoïde des décompositions restreintes, un outil pour le produit de langagesde tuiles linéaires. / Tiles are finite, linear or tree-like structures, with a notion of overlapping.In computer science, they offer a useful way to represent musical objects,as studied by Janin [2016]. We will study the sets of tiles, especially asrepresentations of algebraic objects, based on the theory of inverse semigroups.Our main focus will be languages of tiles, and the appropriate recognizers,than can be defined by the adaptation to tiles of well-known notions over languagesof words. We will look into the recognition by automata, by presentingautomata over linear and tree-like tiles. We will remark the limits of the powerof such automata.While the notion of recognizability by morphisms is unsuitable to languagesof tiles, we will define recognizability by premorphisms, or quasi-recognizability.We will study the links between quasi-recognizability and recognizability bytile automata.We will finally look into the closure properties of the set of tile languages recognizedby automata, and of the set of quasi-recognizable languages. The lastpart will be dedicated to linear tiles, and will present the monoid of restricteddecompositions, a tool for the product of linear tile languages.

Il s'agit d'utiliser par la production de logiciels effectivement opérationnels, les techniques graphiques interactives dans le domaine de l'analyse structurale de système. On s'est orienté plus précisément vers une catégorie précise de représentation des systèmes: les graphes.

Cette thèse se situe à l'interface de trois grands domaines : la combinatoire des mots, la théorie des automates et la théorie des nombres. Plus précisément, nous montrons comment des outils provenant de la combinatoire des mots et de la théorie des automates interviennent dans l'étude de problèmes arithmétiques concernant les séries formelles à coefficients dans un corps fini.Le point de départ de cette thèse est un célèbre théorème de Christol qui caractérise les séries de Laurent algébriques sur le corps F_q(T), l'entier q désignant une puissance d'un nombre premier p, en termes d'automates finis et dont l'énoncé est : " Une série de Laurent à coefficients dans le corps fini F_q est algébrique si et seulement si la suite de ses coefficients est engendrée par un p-automate fini ". Ce résultat, qui révèle dans un certain sens la simplicité de ces séries de Laurent, a donné naissance à des travaux importants parmi lesquels de nombreuses applications et généralisations.L'objet principal de cette thèse est, dans un premier temps, d'exploiter la simplicité de séries de Laurent algébriques à coefficients dans un corps fini afin d'obtenir des résultats diophantiens, puis d'essayer d'étendre cette étude à des fonctions transcendantes arithmétiquement intéressantes. Nous nous concentrons tout d'abord sur une classe de séries de Laurent algébriques particulières qui généralisent la fameuse cubique de Baum et Sweet. Le résultat principal obtenu pour ces dernières est une description explicite de leur développement en fraction continue, généralisant ainsi certains travaux de Mills et Robbins. Rappelons que le développement en fraction continue permet généralement d'obtenir des informations très précises sur l'approximation rationnelle ; les meilleures approximations étant obtenues directement à partir de la suite des quotients partiels. Malheureusement, il est souvent très difficile d'obtenir le développement en fraction continue d'une série de Laurent algébrique, que celle-ci soit donné par une équation algébrique ou par son développement en série de Laurent. La deuxième étude que nous présentons dans cette thèse fournit une information diophantienne à priori moins précise que la description du développement en fraction continue, mais qui a le mérite de concerner toutes les séries de Laurent algébriques (à coefficients dans un corps fini). L'idée principale est d'utiliser l'automaticité de la suite des coefficients de ces séries de Laurent afin d'obtenir une borne générale pour leur exposant d'irrationalité. Malgré la généralité de ce résultat, la borne obtenue n'est pas toujours satisfaisante. Dans certains cas, elle peut s'avérer plus mauvaise que celle provenant de l'inégalité de Mahler. Cependant, dans de nombreuses situations, il est possible d'utiliser notre approche pour fournir, au mieux, la valeur exacte de l'exposant d'irrationalité, sinon des encadrements très précis de ce dernier.Dans un dernier travail nous nous plaçons dans un cadre plus général que celui des séries de Laurent algébriques, à savoir celui des séries de Laurent dont la suite des coefficients a une " basse complexité ". Nous montrons que cet ensemble englobe quelques fonctions remarquables, comme les séries algébriques et l'inverse de l'analogue du nombre \pi dans le module de Carlitz. Il possède, par ailleurs, des propriétés de stabilité intéressantes : entre autres, il s'agit d'un espace vectoriel sur le corps des fractions rationnelles à coefficients dans un corps fini (ce qui, d'un point de vue arithmétique, fournit un critère d'indépendance linéaire), il est de plus laissé invariant par diverses opérations classiques comme le produit de Hadamard

Cette thèse porte sur des minorants pour des mesures de complexité liées à des sous-classes de la classe P de langages pouvant être décidés en temps polynomial par des machines de Turing. Nous considérons des modèles de calcul non uniformes tels que les programmes sur monoïdes et les programmes de branchement. Notre première contribution est un traitement abstrait de la méthode de Nečiporuk pour prouver des minorants, indépendamment de toute mesure de complexité spécifique. Cette méthode donne toujours les meilleurs minorants connus pour des mesures telles que la taille des programmes de branchements déterministes et non déterministes ou des formules avec des opérateurs booléens binaires arbitraires ; nous donnons une formulation abstraite de la méthode et utilisons ce cadre pour démontrer des limites au meilleur minorant obtenable en utilisant cette méthode pour plusieurs mesures de complexité. Par là, nous confirmons, dans ce cadre légèrement plus général, des résultats de limitation précédemment connus et exhibons de nouveaux résultats de limitation pour des mesures de complexité auxquelles la méthode de Nečiporuk n'avait jamais été appliquée. Notre seconde contribution est une meilleure compréhension de la puissance calculatoire des programmes sur monoïdes issus de petites variétés de monoïdes finis. Les programmes sur monoïdes furent introduits à la fin des années 1980 par Barrington et Thérien pour généraliser la reconnaissance par morphismes et ainsi obtenir une caractérisation en termes de semi-groupes finis de NC^1 et de ses sous-classes. Étant donné une variété V de monoïdes finis, on considère la classe P(V) de langages reconnus par une suite de programmes de longueur polynomiale sur un monoïde de V : lorsque l'on fait varier V parmi toutes les variétés de monoïdes finis, on obtient différentes sous-classes de NC^1, par exemple AC^0, ACC^0 et NC^1 quand V est respectivement la variété de tous les monoïdes apériodiques finis, résolubles finis et finis. Nous introduisons une nouvelle notion de docilité pour les variétés de monoïdes finis, renforçant une notion de Péladeau. L'intérêt principal de cette notion est que quand une variété V de monoïdes finis est docile, nous avons que P(V) contient seulement des langages réguliers qui sont quasi reconnus par morphisme par des monoïdes de V. De nombreuses questions ouvertes à propos de la structure interne de NC^1 seraient réglées en montrant qu'une variété de monoïdes finis appropriée est docile, et, dans cette thèse, nous débutons modestement une étude exhaustive de quelles variétés de monoïdes finis sont dociles. Plus précisément, nous portons notre attention sur deux petites variétés de monoïdes apériodiques finis bien connues : DA et J. D'une part, nous montrons que DA est docile en utilisant des arguments de théorie des semi-groupes finis. Cela nous permet de dériver une caractérisation algébrique exacte de la classe des langages réguliers dans P(DA). D'autre part, nous montrons que J n'est pas docile. Pour faire cela, nous présentons une astuce par laquelle des programmes sur monoïdes de J peuvent reconnaître beaucoup plus de langages réguliers que seulement ceux qui sont quasi reconnus par morphisme par des monoïdes de J. Cela nous amène à conjecturer une caractérisation algébrique exacte de la classe de langages réguliers dans P(J), et nous exposons quelques résultats partiels appuyant cette conjecture. Pour chacune des variétés DA et J, nous exhibons également une hiérarchie basée sur la longueur des programmes à l'intérieur de la classe des langages reconnus par programmes sur monoïdes de la variété, améliorant par là les résultats de Tesson et Thérien sur la propriété de longueur polynomiale pour les monoïdes de ces variétés. / This thesis deals with lower bounds for complexity measures related to subclasses of the class P of languages that can be decided by Turing machines in polynomial time. We consider non-uniform computational models like programs over monoids and branching programs.Our first contribution is an abstract, measure-independent treatment of Nečiporuk's method for proving lower bounds. This method still gives the best lower bounds known on measures such as the size of deterministic and non-deterministic branching programs or formulae{} with arbitrary binary Boolean operators; we give an abstract formulation of the method and use this framework to prove limits on the best lower bounds obtainable using this method for several complexity measures. We thereby confirm previously known limitation results in this slightly more general framework and showcase new limitation results for complexity measures to which Nečiporuk's method had never been applied.Our second contribution is a better understanding of the computational power of programs over monoids taken from small varieties of finite monoids. Programs over monoids were introduced in the late 1980s by Barrington and Thérien as a way to generalise recognition by morphisms so as to obtain a finite-semigroup-theoretic characterisation of NC^1 and its subclasses. Given a variety V of finite monoids, one considers the class P(V) of languages recognised by a sequence of polynomial-length programs over a monoid from V: as V ranges over all varieties of finite monoids, one obtains different subclasses of NC^1, for instance AC^0, ACC^0 and NC^1 when V respectively is the variety of all finite aperiodic, finite solvable and finite monoids. We introduce a new notion of tameness for varieties of finite monoids, strengthening a notion of Péladeau. The main interest of this notion is that when a variety V of finite monoids is tame, we have that P(V) does only contain regular languages that are quasi morphism-recognised by monoids from V. Many open questions about the internal structure of NC^1 would be settled by showing that some appropriate variety of finite monoids is tame, and, in this thesis, we modestly start an exhaustive study of which varieties of finite monoids are tame. More precisely, we focus on two well-known small varieties of finite aperiodic monoids: DA and J. On the one hand, we show that DA is tame using finite-semigroup-theoretic arguments. This allows us to derive an exact algebraic characterisation of the class of regular languages in P(DA). On the other hand, we show that J is not tame. To do this, we present a trick by which programs over monoids from J can recognise much more regular languages than only those that are quasi morphism-recognised by monoids from J. This brings us to conjecture an exact algebraic characterisation of the class of regular languages in P(J), and we lay out some partial results that support this conjecture. For each of the varieties DA and J, we also exhibit a program-length-based hierarchy within the class of languages recognised by programs over monoids from the variety, refining Tesson and Thérien's results on the polynomial-length property for monoids from those varieties.

No description available.

Cette thèse se situe à l'interface de trois grands domaines : la combinatoire des mots, la théorie des automates et la théorie des nombres. Plus précisément, nous montrons comment des outils provenant de la combinatoire des mots et de la théorie des automates interviennent dans l'étude de problèmes arithmétiques concernant les séries formelles à coefficients dans un corps fini.Le point de départ de cette thèse est un célèbre théorème de Christol qui caractérise les séries de Laurent algébriques sur le corps F_q(T), l'entier q désignant une puissance d'un nombre premier p, en termes d'automates finis et dont l'énoncé est : « Une série de Laurent à coefficients dans le corps fini F_q est algébrique si et seulement si la suite de ses coefficients est engendrée par un p-automate fini ». Ce résultat, qui révèle dans un certain sens la simplicité de ces séries de Laurent, a donné naissance à des travaux importants parmi lesquels de nombreuses applications et généralisations.L'objet principal de cette thèse est, dans un premier temps, d'exploiter la simplicité de séries de Laurent algébriques à coefficients dans un corps fini afin d'obtenir des résultats diophantiens, puis d'essayer d'étendre cette étude à des fonctions transcendantes arithmétiquement intéressantes. Nous nous concentrons tout d'abord sur une classe de séries de Laurent algébriques particulières qui généralisent la fameuse cubique de Baum et Sweet. Le résultat principal obtenu pour ces dernières est une description explicite de leur développement en fraction continue, généralisant ainsi certains travaux de Mills et Robbins. Rappelons que le développement en fraction continue permet généralement d'obtenir des informations très précises sur l'approximation rationnelle ; les meilleures approximations étant obtenues directement à partir de la suite des quotients partiels. Malheureusement, il est souvent très difficile d'obtenir le développement en fraction continue d'une série de Laurent algébrique, que celle-ci soit donné par une équation algébrique ou par son développement en série de Laurent. La deuxième étude que nous présentons dans cette thèse fournit une information diophantienne à priori moins précise que la description du développement en fraction continue, mais qui a le mérite de concerner toutes les séries de Laurent algébriques (à coefficients dans un corps fini). L'idée principale est d'utiliser l'automaticité de la suite des coefficients de ces séries de Laurent afin d'obtenir une borne générale pour leur exposant d'irrationalité. Malgré la généralité de ce résultat, la borne obtenue n'est pas toujours satisfaisante. Dans certains cas, elle peut s'avérer plus mauvaise que celle provenant de l'inégalité de Mahler. Cependant, dans de nombreuses situations, il est possible d'utiliser notre approche pour fournir, au mieux, la valeur exacte de l'exposant d'irrationalité, sinon des encadrements très précis de ce dernier.Dans un dernier travail nous nous plaçons dans un cadre plus général que celui des séries de Laurent algébriques, à savoir celui des séries de Laurent dont la suite des coefficients a une « basse complexité ». Nous montrons que cet ensemble englobe quelques fonctions remarquables, comme les séries algébriques et l'inverse de l'analogue du nombre \pi dans le module de Carlitz. Il possède, par ailleurs, des propriétés de stabilité intéressantes : entre autres, il s'agit d'un espace vectoriel sur le corps des fractions rationnelles à coefficients dans un corps fini (ce qui, d'un point de vue arithmétique, fournit un critère d'indépendance linéaire), il est de plus laissé invariant par diverses opérations classiques comme le produit de Hadamard / This thesis looks at the interplay of three important domains: combinatorics on words, theory of finite-state automata and number theory. More precisely, we show how tools coming from combinatorics on words and theory of finite-state automata intervene in the study of arithmetical problems concerning the Laurent series with coefficients in a finite field.The starting point of this thesis is a famous theorem of Christol which characterizes algebraic Laurent series over the field F_q(T), q being a power of the prime number p, in terms of finite-state automata and whose statement is the following : “A Laurent series with coefficients in a finite field F_q is algebraic over F_q(T) if and only if the sequence of its coefficients is p-automatic”.This result, which reveals, somehow, the simplicity of these Laurent series, has given rise to important works including numerous applications and generalizations. The theory of finite-state automata and the combinatorics on words naturally occur in number theory and, sometimes, prove themselves to be indispensable in establishing certain important results in this domain.The main purpose of this thesis is, foremost, to exploit the simplicity of the algebraic Laurent series with coefficients in a finite field in order to obtain some Diophantine results, then to try to extend this study to some interesting transcendental functions. First, we focus on a particular set of algebraic Laurent series that generalize the famous cubic introduced by Baum and Sweet. The main result we obtain concerning these Laurent series gives the explicit description of its continued fraction expansion, generalizing therefore some articles of Mills and Robbins.Unfortunately, it is often very difficult to find the continued fraction representation of a Laurent series, whether it is given by an algebraic equation or by its Laurent series expansion. The second study that we present in this thesis provides a Diophantine information which, although a priori less complete than the continued fraction expansion, has the advantage to characterize any algebraic Laurent series. The main idea is to use some the automaticity of the sequence of coefficients of these Laurent series in order to obtain a general bound for their irrationality exponent. In the last part of this thesis we focus on a more general class of Laurent series, namely the one of Laurent series of “low” complexity. We prove that this set includes some interesting functions, as for example the algebraic series or the inverse of the analogue of the real number \pi. We also show that this set satisfy some nice closure properties : in particular, it is a vector space over the field over F_q(T).

Cette thèse se situe en combinatoire algébrique, et plus particulièrement en théorie combinatoire des représentations linéaires des monoïdes finis.Rappelons qu'un monoïde est un ensemble fini M muni d'une multiplication et d'un élément neutre, et qu'une représentation de M est un morphisme de M dans le monoïde des matrices $M_n(ck)$ où $ck$ est un corps, typiquement $ck =CC$. Les résultats des dernières décennies donnent un contrôle assez fin sur les représentations des monoïdes, permettant souvent de se ramener à de la théorie des représentations des groupes et de la combinatoire sur des préordres.En 1996, Krob et Thibon ont montré que l'induction et la restriction des représentations irréductibles et projectives de la tour des $0$-algèbres de Hecke $H_n(0)$ permet de munir l'ensemble des caractères d'une structure d'algèbre de Hopf, qui est isomorphe a l'algèbre de Hopf $ncsf$ des fonctions symétriques non commutatives. Cela donne une emph{catégorification} de$ncsf$, c'est-à-dire une interprétation de celle-ci en terme de théorie des représentations. Ils prolongent ainsi un résultat dû à Frobenius établissant un lien entre l'anneau des caractères de la tour des groupes symétriques et lesfonctions symétriques. Un problème naturel depuis lors est d'essayer de catégorifier d'autres algèbres de Hopf -- par exemple l'algèbre $pbt$ desarbres binaires de Loday et Ronco -- par des tours d'algèbres.Deviner une telle tour d'algèbres est difficile en général. Dans le cadre de cemanuscrit on restreint le champ de recherche aux tours de monoïdes, afin de mieux contrôler leurs représentations. C'est naturel car ce cadre couvre enfait les deux exemples fondamentaux ci-dessus, tandis qu'il est impossible decatégorifier $ncsf$ avec seulement une tour de groupes.Nous commençons par donner quelques résultats sur les représentations des toursde monoïdes. Ensuite, nous nous intéressons à la catégorification par destours de semi-treillis, et en particulier de quotients du permutoèdre. Avecceux-ci, nous catégorifions la structure de cogèbre de $fqsym$ sur la base$gbasis$ et celle d'algèbre de $fqsym$ sur la base $fbasis$. Cela ne permetcependant pas de catégorifier simultanément toute la structure de Hopf de ces algèbres. Dans un second temps, nous menons une recherche exhaustive des catégorifications de $pbt$. Nous montrons que, sous des hypothèses naturelles,il n'existe pas de catégorification de $pbt$ par une tour de monoïdesapériodiques. Enfin, nous démontrons que, dans un certain sens, la tour des monoïdes $0$-Hecke est la tour de monoïdes la plus simple catégorifiant $ncsf$.La seconde partie porte sur les fonctions de parking, par application des résultats de la première partie. D'une part, nous étudions la théorie des représentations de la tour des fonctions de parking croissantes. D'autre part,dans un travail commun avec Jean-Baptiste Priez nous reprenons une généralisation des fonctions de parking due à Stanley et Pitman. Afin d'obtenir des formules d'énumérations, nous utilisons une variante -- plus efficace dansle cas présent -- de la théorie des espèces. Nous donnons une action de$H_n(0)$ (et non du groupe symétrique) sur les fonctions de parking généralisées, et utilisons le théorème de catégorification de Krob et Thibon,pour relever dans les fonctions symétriques non commutatives le caractère de cette action. / This thesis is focused on combinatorical representation theory of finitemonoids within the field of algebraic combinatorics.A monoid $M$ is a finite set endowed with a multiplication and a neutralelement. A representation of $M$ is a morphism from $M$ into the monoid ofmatrices $M_n(ck)$ where $ck$ is a field; in this work it will typically bereferred to as $ck = CC$.The results obtained in the last decades allows us to use representation theoryof groups, and combinatorics on preorders in order to explore representationtheory of finite monoides.In 1996, Krob and Thibon proved that the induction and restriction rules ofirreducible and projective representations of the tower of $0$-Hecke monoidsendows its ring of caracters with a Hopf algebra structure, isomorph to thenon-commutative symmetric functions Hopf algebra $ncsf$. This gives acategorification of $ncsf$, which is an interpretation of the non-commutativesymmetruc functions in the language of representation theory. This extends atheorem of Frobenius endowing the character ring of symmetric groups to theHopf algebra of symmetric functions. Since then a natural problem is tocategorify other Hopf algebras -- for instance the Planar Binary Tree algebraof Loday and Ronco -- by a tower of algebras.Guessing such a tower of algebra is a difficult problem in general.In this thesis we restrict ourselves to towers of monoids in order to have abetter control on its representations. This is quite natural as on one hand,this setup covers both previous fundamental examples, whereas $ncsf$cannot be categorified in the restricted set of tower of group algebras.In the first part of this work, we start with some results about representationtheory of towers of monoids. We then focus on categorification with towers ofsemilatices, for example the tower of permutohedrons. We categorify thealgebra, and cogebra structure of $fqsym$, but not the full Hopf algebrastructure with its dual. We then make a comprehensive search in order tocategorify $pbt$ with a tower of monoids. We show that under naturalhypothesis, there exists no tower of monoids satisfying the categorificationaxioms. Finally we show that in some sense, the tower of $0$-Hecke monoids isthe simplest tower categorifying $ncsf$.The second part of this work deals with parking functions, applying resultsfrom the first part. We first study the representation theory of non decreasingparking functions. We then present a joint work with Jean-Baptiste Priez on ageneralization of parking functions from Pitman and Stanley. To obtainenumeration formulas, we use a variant of the species theory which was moreefficient in our case.We used an action of $H_n(0)$ instead of the symmetric group and use theKrob-Thibon theorem to lift the character of this action into the Hopf algebraof non-commutative symmetric functions.

Cette thèse développe des algorithmes pour les problèmes de plus court chemin sous cont-rain-tes de ressources, et les applique à l'optimisation des rotations des avions et des équipages d'une compagnie aérienne dans le cadre d'approches par génération de colonnes.Les problèmes de plus court chemin sous contraintes de ressources sont généralement résolus grâce à une énumération intelligente de tous les chemins non dominés. Les approches récentes utilisent des bornes sur les ressources des chemins pour éliminer des solutions partielles. L'efficacité de la méthode est conditionnée par la qualité des bornes utilisées. Notre principale contribution au domaine est l'introduction d'une procédure générique pour calculer des bornes qui s'applique à la plupart des problèmes de chemins sous contraintes, et en particulier les problèmes stochastiques. A cette fin, nous introduisons une généralisation du problème de plus court chemin sous contraintes dans laquelle les ressources des chemins appartiennent à un monoïde ordonné comme un treillis. La ressource d'un chemin est la somme des ressources de ses arcs, le terme somme désignant l'opérateur du monoïde. Le problème consiste à trouver parmi les chemins qui satisfont une contrainte donnée celui dont la ressource minimise une fonction de coût croissante de la ressource des chemins. Nous généralisons les algorithmes d'énumération à ce nouveau problème. La théorie des treillis nous permet de construire une procédure polynomiale pour trouver des bornes de qualité. L'efficacité pratique de la méthode est évaluée au travers d'une étude numérique détaillée sur des problèmes de chemins déterministes et stochastiques. Les procédures de calcul des bornes peuvent être interprétées comme des généralisations aux monoïdes ordonnés comme des treillis d'algorithmes de la littérature définis pour résoudre un problème de chemin pour lequel les ressources des chemins prennent leur valeur dans un semi-anneau.Nos algorithmes de chemins ont été appliqués avec succès au problème de crew pairing. Étant donné un ensemble de vols opérés par une compagnie aérienne, les problèmes d'aircraft routing et de crew pairing construisent respectivement les séquences de vols opérées par les avions et par les équipages de manière à couvrir tous les vols à moindre coût. Comme certaines séquences de vols ne peuvent être réalisées par un équipage que s'il reste dans le même avion, les deux problèmes sont liés. La pratique actuelle dans l'industrie aéronautique est de résoudre tout d'abord le problème d'aircraft routing, puis le problème de crew pairing, ce qui aboutit à une solution non-optimale. Des méthodes de résolution pour le problème intégré ont été développées ces dix dernières années. Nous proposons une méthode de résolution pour le problème intégré reposant sur deux nouveaux ingrédients : un programme linéaire en nombre entier compact pour le problème d'aircraft routing, ainsi que de nouveaux pour le problème esclave de l'approche usuelle par génération de colonnes du problème de crew pairing. Ces algorithmes pour le problème esclave sont une application de nos algorithmes pour le problème de plus court chemin sous contraintes. Nous généralisons ensuite cette approche de manière à prendre en compte des contraintes de probabilités sur la propagation du retard. Ces algorithmes permettent de résoudre quasiment à l'optimum les instances industrielles d'Air France / This thesis develops algorithms for resource constrained shortest path problems, and uses them to solve the pricing subproblems of column generation approaches to some airline operations problems.Resource constrained shortest path problems are usually solved using a smart enumeration of the non-dominated paths. Recent improvements of these enumeration algorithms rely on the use of bounds on path resources to discard partial solutions. The quality of the bounds determines the performance of the algorithm. Our main contribution to the topic is to introduce a standard procedure to generate bounds on paths resources in a general setting which covers most resource constrained shortest path problems, among which stochastic versions. In that purpose, we introduce a generalization of the resource constrained shortest path problem where the resources are taken in a lattice ordered monoid. The resource of a path is the monoid sum of the resources of its arcs. The problem consists in finding a path whose resource minimizes a non-decreasing cost function of the path resource among the paths that satisfy a given constraint. Enumeration algorithms are generalized to this framework. We use lattice theory to provide polynomial procedures to find good quality bounds. The efficiency of the approach is proved through an extensive numerical study on deterministic and stochastic path problems. Interestingly, the bounding procedures can be seen as generalizations to lattice ordered monoids of some algebraic path problem algorithms which initially work with resources in a semiring.Given a set of flight legs operated by an airline, the aircraft routing and the crew pairing problem build respectively the sequences of flight legs operated by airplanes and crews at minimum cost. As some sequences of flight legs can be operated by crews only if they stay in the same aircraft, the two problems are linked. The current practice in the industry is to solve first the aircraft routing, and then the crew pairing problem, leading to a non-optimal solution. During the last decade, solution schemes for the integrated problem have been developed. We propose a solution scheme for the integrated problem based on two new ingredients: a compact integer program approach to the aircraft routing problem, and a new algorithm for the pricing subproblem of the usual column generation approach to the crew pairing problem, which is based on our resource constrained shortest path framework. We then generalize the algorithm to take into account delay propagation through probabilistic constraints. The algorithms enable to solve to near optimality Air France industrial instances