Relevant bibliographies by topics / Algorithmic and combinatorics of monoids

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers

Academic literature on the topic 'Algorithmic and combinatorics of monoids'

Author: Grafiati
Published: 25 May 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Algorithmic and combinatorics of monoids.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Algorithmic and combinatorics of monoids"

1

Cain, Alan J., António Malheiro, and Fábio M. Silva. "Combinatorics of patience sorting monoids." Discrete Mathematics 342, no. 9 (September 2019): 2590–611. http://dx.doi.org/10.1016/j.disc.2019.05.022.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Abbes, S., S. Gouëzel, V. Jugé, and J. Mairesse. "Asymptotic combinatorics of Artin–Tits monoids and of some other monoids." Journal of Algebra 525 (May 2019): 497–561. http://dx.doi.org/10.1016/j.jalgebra.2019.01.019.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

DIEKERT, VOLKER, NICOLE ONDRUSCH, and MARKUS LOHREY. "ALGORITHMIC PROBLEMS ON INVERSE MONOIDS OVER VIRTUALLY FREE GROUPS." International Journal of Algebra and Computation 18, no. 01 (February 2008): 181–208. http://dx.doi.org/10.1142/s0218196708004366.

Full text
Abstract:
Let G be a finitely generated virtually-free group. We consider the Birget–Rhodes expansion of G, which yields an inverse monoid and which is denoted by IM (G) in the following. We show that for a finite idempotent presentation P, the word problem of a quotient monoid IM (G)/P can be solved in linear time on a RAM. The uniform word problem, where G and the presentation P are also part of the input, is EXPTIME-complete. With IM (G)/P we associate a relational structure, which contains for every rational subset L of IM (G)/P a binary relation, consisting of all pairs (x,y) such that y can be obtained from x by right multiplication with an element from L. We prove that the first-order theory of this structure is decidable. This result implies that the emptiness problem for Boolean combinations of rational subsets of IM (G)/P is decidable, which, in turn implies the decidability of the submonoid membership problem of IM (G)/P. These results were known previously for free groups, only. Moreover, we provide a new algorithmic approach for these problems, which seems to be of independent interest even for free groups. We also show that one cannot expect decidability results in much larger frameworks than virtually-free groups because the subgroup membership problem of a subgroup H in an arbitrary group G can be reduced to a word problem of some IM (G)/P, where P depends only on H. A consequence is that there is a hyperbolic group G and a finite idempotent presentation P such that the word problem is undecidable for some finitely generated submonoid of IM (G)/P. In particular, the word problem of IM (G)/P is undecidable.
APA, Harvard, Vancouver, ISO, and other styles
4

Hurwitz, Carol M. "On the homotopy theory of monoids." Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics 47, no. 2 (October 1989): 171–85. http://dx.doi.org/10.1017/s1446788700031621.

Full text
Abstract:
AbsractIn this paper, it is shown that any connected, small category can be embedded in a semi-groupoid (a category in which there is at least one isomorphism between any two elements) in such a way that the embedding includes a homotopy equivalence of classifying spaces. This immediately gives a monoid whose classifying space is of the same homotopy type as that of the small category. This construction is essentially algorithmic, and furthermore, yields a finitely presented monoid whenever the small category is finitely presented. Some of these results are generalizations of ideas of McDuff.
APA, Harvard, Vancouver, ISO, and other styles
5

BLANCHET-SADRI, F. "ALGORITHMIC COMBINATORICS ON PARTIAL WORDS." International Journal of Foundations of Computer Science 23, no. 06 (September 2012): 1189–206. http://dx.doi.org/10.1142/s0129054112400473.

Full text
Abstract:
Algorithmic combinatorics on partial words, or sequences of symbols over a finite alphabet that may have some do-not-know symbols or holes, has been developing in the past few years. Applications can be found, for instance, in molecular biology for the sequencing and analysis of DNA, in bio-inspired computing where partial words have been considered for identifying good encodings for DNA computations, and in data compression. In this paper, we focus on two areas of algorithmic combinatorics on partial words, namely, pattern avoidance and subword complexity. We discuss recent contributions as well as a number of open problems. In relation to pattern avoidance, we classify all binary patterns with respect to partial word avoidability, we classify all unary patterns with respect to hole sparsity, and we discuss avoiding abelian powers in partial words. In relation to subword complexity, we generate and count minimal Sturmian partial words, we construct de Bruijn partial words, and we construct partial words with subword complexities not achievable by full words (those without holes).
APA, Harvard, Vancouver, ISO, and other styles
6

RENNER, LEX E. "DISTRIBUTION OF PRODUCTS IN FINITE MONOIDS I: COMBINATORICS." International Journal of Algebra and Computation 09, no. 06 (December 1999): 693–708. http://dx.doi.org/10.1142/s0218196799000394.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Okniński, Jan, and Magdalena Wiertel. "Combinatorics and structure of Hecke–Kiselman algebras." Communications in Contemporary Mathematics 22, no. 07 (June 15, 2020): 2050022. http://dx.doi.org/10.1142/s0219199720500224.

Full text
Abstract:
Hecke–Kiselman monoids [Formula: see text] and their algebras [Formula: see text], over a field [Formula: see text], associated to finite oriented graphs [Formula: see text] are studied. In the case [Formula: see text] is a cycle of length [Formula: see text], a hierarchy of certain unexpected structures of matrix type is discovered within the monoid [Formula: see text] and this hierarchy is used to describe the structure and the properties of the algebra [Formula: see text]. In particular, it is shown that [Formula: see text] is a right and left Noetherian algebra, while it has been known that it is a PI-algebra of Gelfand–Kirillov dimension one. This is used to characterize all Noetherian algebras [Formula: see text] in terms of the graphs [Formula: see text]. The strategy of our approach is based on the crucial role played by submonoids of the form [Formula: see text] in combinatorics and structure of arbitrary Hecke–Kiselman monoids [Formula: see text].
APA, Harvard, Vancouver, ISO, and other styles
8

ROSALES, J. C., P. A. GARCÍA-SÁNCHEZ, and J. I. GARCÍA-GARCÍA. "PRESENTATIONS OF FINITELY GENERATED SUBMONOIDS OF FINITELY GENERATED COMMUTATIVE MONOIDS." International Journal of Algebra and Computation 12, no. 05 (October 2002): 659–70. http://dx.doi.org/10.1142/s021819670200105x.

Full text
Abstract:
We give an algorithmic method for computing a presentation of any finitely generated submonoid of a finitely generated commutative monoid. We use this method also for calculating the intersection of two congruences on ℕp and for deciding whether or not a given finitely generated commutative monoid is t-torsion free and/or separative. The last section is devoted to the resolution of some simple equations on a finitely generated commutative monoid.
APA, Harvard, Vancouver, ISO, and other styles
9

Garg, Vijay K. "Algorithmic combinatorics based on slicing posets." Theoretical Computer Science 359, no. 1-3 (August 2006): 200–213. http://dx.doi.org/10.1016/j.tcs.2006.03.005.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Polo, Harold. "Approximating length-based invariants in atomic Puiseux monoids." Algebra and Discrete Mathematics 33, no. 1 (2022): 128–39. http://dx.doi.org/10.12958/adm1760.

Full text
Abstract:
A numerical monoid is a cofinite additive submonoid of the nonnegative integers, while a Puiseux monoid is an additive submonoid of the nonnegative cone of the rational numbers. Using that a Puiseux monoid is an increasing union of copies of numerical monoids, we prove that some of the factorization invariants of these two classes of monoids are related through a limiting process. This allows us to extend results from numerical to Puiseux monoids. We illustrate the versatility of this technique by recovering various known results about Puiseux monoids.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Algorithmic and combinatorics of monoids"

1

Charles, Balthazar. "Combinatorics and computations : Cartan matrices of monoids & minimal elements of Shi arrangements." Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG063.

Full text
Abstract:
Cette thèse présente le résultat de recherches sur deux thèmes combinatoires distincts: le calcul effectif des matrices de Cartan en théorie des représentations des monoïdes et l'exploration des propriétés des éléments minimaux dans les arrangements de Shi des groupes de Coxeter. Bien que disparates, ces deux domaines de recherche partagent l'utilisation de méthodes combinatoires et d'exploration informatique, soit en tant que fin en soi pour le premier domaine, soit comme aide à la recherche pour le second. Dans la première partie de la thèse, nous développons des méthodes pour le calcul effectif des tables de caractères et des matrices de Cartan dans la théorie des représentations des monoïdes. À cette fin, nous présentons un algorithme basé sur nos résultats pour le calcul efficace des points fixes sous une action similaire à une conjugaison, dans le but de mettre en œuvre la formule de [Thiéry '12] pour la matrice de Cartan. Après une introduction largement auto-contenue aux notions nécessaires, nous présentons nos résultats sur le comptage des points fixes, ainsi qu'une nouvelle formule pour la table de caractères des monoïdes finis. Nous évaluons les performances des algorithmes résultants en termes de temps d'exécution et d'utilisation mémoire. Nous observons qu'ils sont plus efficaces par plusieurs ordres de grandeur que les algorithmes non spécialisés pour les monoïdes. Nous espérons que l'implémentation (publique) résultant de ces travaux contribuera à la communauté des représentations des monoïdes en permettant des calculs auparavant difficiles. La deuxième partie de la thèse se concentre sur les propriétés des éléments minimaux dans les arrangements de Shi. Les arrangements de Shi ont été introduits dans [Shi '87] et sont l'objet de la Conjecture 2 dans [Dyer, Hohlweg '14]. Initialement motivés par cette conjecture, après une introduction aux notions nécessaires, nous présentons deux résultats. Premièrement, une démonstration directe dans le cas des groupes de rang 3. Deuxièmement, dans le cas particulier des groupes de Weyl, nous donnons une description des éléments minimaux des régions de Shi en étendant une bijection issue de [Athanasiadis, Linusson '99] et [Armstrong, Reiner, Rhoades '15] entre les fonctions de parking et les régions de Shi permettant d'effectuer le calcul pratique des éléments minimaux. Comme application, à partir des propriétés de ce calcul, nous donnons une démonstration de la conjecture pour les groupes de Weyl indépendante de leur classification. Ces résultats révèlent une interaction intrigante entre les partitions non-croisées et non-embrassées dans le cas des groupes de Weyl classiques
This thesis presents an investigation into two distinct combinatorial subjects: the effective computation of Cartan matrices in monoid representation theory and the exploration of properties of minimal elements in Shi arrangements of Coxeter groups. Although disparate, both of these research focuses share a commonality in the utilization of combinatorial methods and computer exploration either as an end in itself for the former or as a help to research for the latter. In the first part of the dissertation, we develop methods for the effective computation of character tables and Cartan matrices in monoid representation theory. To this end, we present an algorithm based on our results for the efficient computations of fixed points under a conjugacy-like action, with the goal to implement Thiéry's formula for the Cartan matrix from [Thiéry '12]. After a largely self-contained introduction to the necessary background, we present our results for fixed-point counting, as well as a new formula for the character table of finite monoids. We evaluate the performance of the resulting algorithms in terms of execution time and memory usage and find that they are more efficient than algorithms not specialized for monoids by orders of magnitude. We hope that the resulting (public) implementation will contribute to the monoid representation community by allowing previously impractical computations. The second part of the thesis focuses on the properties of minimal elements in Shi arrangements. The Shi arrangements were introduced in [Shi '87] and are the object of Conjecture 2 from [Dyer, Hohlweg '14]. Originally motivated by this conjecture, we present two results. Firstly, a direct proof in the case of rank 3 groups. Secondly, in the special case of Weyl groups, we give a description of the minimal elements of the Shi regions by extending a bijection from [Athanasiadis, Linusson '99] and [Armstrong, Reiner, Rhoades '15] between parking functions and Shi regions. This allows for the effective computation of the minimal elements. From the properties of this computation, we provide a type-free proof of the conjecture in Weyl groups as an application. These results reveal an intriguing interplay between the non-nesting and non-crossing worlds in the case of classical Weyl groups
APA, Harvard, Vancouver, ISO, and other styles
2

Gay, Joël. "Representation of Monoids and Lattice Structures in the Combinatorics of Weyl Groups." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLS209/document.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
3

Fenner, Peter. "Some algorithmic problems in monoids of Boolean matrices." Thesis, University of Manchester, 2018. https://www.research.manchester.ac.uk/portal/en/theses/some-algorithmic-problems-in-monoids-of-boolean-matrices(d9cc2975-fa24-42c9-8505-5accaaa2a73e).html.

Full text
Abstract:
A Boolean matrix is a matrix with elements from the Boolean semiring ({0, 1}, +, x), where the addition and multiplication are as usual with the exception that 1 + 1 = 1. In this thesis we study eight classes of monoids whose elements are Boolean matrices. Green's relations are five equivalence relations and three pre-orders which are defined on an arbitrary monoid M and describe much of its structure. In the monoids we consider the equivalence relations are uninteresting - and in most cases completely trivial - but the pre-orders are not and play a vital part in understanding the structure of the monoids. Each of the three pre-orders in each of the eight classes of monoids can be viewed as a computational decision problem: given two elements of the monoid, are they related by the pre-order? The main focus of this thesis is determining the computational complexity of each of these twenty-four decision problems, which we successfully do for all but one.
APA, Harvard, Vancouver, ISO, and other styles
4

Emtander, Eric. "Chordal and Complete Structures in Combinatorics and Commutative Algebra." Doctoral thesis, Stockholms universitet, Matematiska institutionen, 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-48241.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
5

Cervetti, Matteo. "Pattern posets: enumerative, algebraic and algorithmic issues." Doctoral thesis, Università degli studi di Trento, 2003. http://hdl.handle.net/11572/311140.

Full text
Abstract:
The study of patterns in combinatorial structures has grown up in the past few decades to one of the most active trends of research in combinatorics. Historically, the study of permutations which are constrained by not containing subsequences ordered in various prescribed ways has been motivated by the problem of sorting permutations with certain devices. However, the richness of this notion became especially evident from its plentiful appearances in several very different disciplines, such as pure mathematics, mathematical physics, computer science, biology, and many others. In the last decades, similar notions of patterns have been considered on discrete structures other than permutations, such as integer sequences, lattice paths, graphs, matchings and set partitions. In the first part of this talk I will introduce the general framework of pattern posets and some classical problems about patterns. In the second part of this talk I will present some enumerative results obtained in my PhD thesis about patterns in permutations, lattice paths and matchings. In particular I will describe a generating tree with a single label for permutations avoiding the vincular pattern 1 - 32 - 4, a finite automata approach to enumerate lattice excursions avoiding a single pattern and some results about matchings avoiding juxtapositions and liftings of patterns.
APA, Harvard, Vancouver, ISO, and other styles
6

Cervetti, Matteo. "Pattern posets: enumerative, algebraic and algorithmic issues." Doctoral thesis, Università degli studi di Trento, 2021. http://hdl.handle.net/11572/311152.

Full text
Abstract:
The study of patterns in combinatorial structures has grown up in the past few decades to one of the most active trends of research in combinatorics. Historically, the study of permutations which are constrained by not containing subsequences ordered in various prescribed ways has been motivated by the problem of sorting permutations with certain devices. However, the richness of this notion became especially evident from its plentiful appearances in several very different disciplines, such as pure mathematics, mathematical physics, computer science,biology, and many others. In the last decades, similar notions of patterns have been considered on discrete structures other than permutations, such as integer sequences, lattice paths, graphs, matchings and set partitions. In the first part of this talk I will introduce the general framework of pattern posets and some classical problems about patterns. In the second part of this talk I will present some enumerative results obtained in my PhD thesis about patterns in permutations, lattice paths and matchings. In particular I will describe a generating tree with a single label for permutations avoiding the vincular pattern 1 - 32 - 4, a finite automata approach to enumerate lattice excursions avoiding a single pattern and some results about matchings avoiding juxtapositions and liftings of patterns.
APA, Harvard, Vancouver, ISO, and other styles
7

Cervetti, Matteo. "Pattern posets: enumerative, algebraic and algorithmic issues." Doctoral thesis, Università degli studi di Trento, 2021. http://hdl.handle.net/11572/311152.

Full text
Abstract:
The study of patterns in combinatorial structures has grown up in the past few decades to one of the most active trends of research in combinatorics. Historically, the study of permutations which are constrained by not containing subsequences ordered in various prescribed ways has been motivated by the problem of sorting permutations with certain devices. However, the richness of this notion became especially evident from its plentiful appearances in several very different disciplines, such as pure mathematics, mathematical physics, computer science, biology, and many others. In the last decades, similar notions of patterns have been considered on discrete structures other than permutations, such as integer sequences, lattice paths, graphs, matchings and set partitions. In the first part of this talk I will introduce the general framework of pattern posets and some classical problems about patterns. In the second part of this talk I will present some enumerative results obtained in my PhD thesis about patterns in permutations, lattice paths and matchings. In particular I will describe a generating tree with a single label for permutations avoiding the vincular pattern 1 - 32 - 4, a finite automata approach to enumerate lattice excursions avoiding a single pattern and some results about matchings avoiding juxtapositions and liftings of patterns.
APA, Harvard, Vancouver, ISO, and other styles
8

Dizona, Jill. "On Algorithmic Fractional Packings of Hypergraphs." Scholar Commons, 2012. http://scholarcommons.usf.edu/etd/4029.

Full text
Abstract:
Let F0 be a fixed k-uniform hypergraph, and let H be a given k-uniform hypergraph on n vertices. An F0-packing of H is a family F of edge-disjoint copies of F0 which are subhypergraphs in H. Let nF0(H) denote the maximum size |F| of an F0-packing F of H. It is well-known that computing nF0(H) is NP-hard for nearly any choice of F0. In this thesis, we consider the special case when F0 is a linear hypergraph, that is, when no two edges of F0 overlap in more than one vertex. We establish for z > 0 and n &ge n0(z) sufficiently large, an algorithm which, in time polynomial in n, constructs an F0-packing F of H of size |F| ≥ nF0(H) - znk. A central direction in our proof uses so-called fractional F0-packings of H which are known to approximate nF0(H). The driving force of our argument, however, is the use and development of several tools within the theory of hypergraph regularity.
APA, Harvard, Vancouver, ISO, and other styles
9

Pépin, Martin. "Quantitative and algorithmic analysis of concurrent programs." Electronic Thesis or Diss., Sorbonne université, 2021. http://www.theses.fr/2021SORUS450.

Full text
Abstract:
Dans cette thèse nous étudions l'espace d'état des programmes concurrents à l'aide des outils de la combinatoire analytique. Dans un premier temps nous analysons une classe de programmes utilisant du parallélisme, du choix non déterministe, des boucles et de la synchronisation de type fork-join. Pour cette classe nous proposons des résultats quantitatifs sur l'explosion combinatoire de l'espace d'état et des outils algorithmiques efficaces de génération aléatoire uniforme d'exécutions. Dans un second temps nous étudions une nouvelle classe de graphes dirigés sans cycles en tant qu'approximation des ordres partiels, eux mêmes modélisant fidèlement le flot de contrôle des programmes concurrents. Pour cette classe nous proposons un algorithme de génération aléatoire uniforme efficace à nombre de sommets et d'arêtes fixés. Finalement, nous étudions aussi des aspects algorithmiques et pratiques de la génération aléatoire dont le champ d'application dépasse le cadre de la concurrence
In this thesis, we study the state space of concurrent programs using the tools from analytic combinatorics. In a first part, we analyse a class of programs featuring parallelism, non-deterministic choices, loops and a fork-join style of synchronisation. For this class, we propose quantitative results regarding the explosion of the state space as well as efficient algorithmic tools for the uniform random generation of executions. In a second part, we study a new class of directed acyclic graphs whose purpose is to approximate partial orders, which are themselves a good model for the control flow of concurrent programs. For this class, we develop an efficient uniform random sampler of graphs with a given number of edges and vertices. Finally, we also study algorithmic and practical aspects of random generation in general whose field of application goes beyond the scope of concurrency
APA, Harvard, Vancouver, ISO, and other styles
10

Virmaux, Aladin. "Théorie des représentations combinatoire de tours de monoïdes : Application à la catégorification et aux fonctions de parking." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLS138/document.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Algorithmic and combinatorics of monoids"

1

Lladser, Manuel E., Robert S. Maier, Marni Mishna, and Andrew Rechnitzer, eds. Algorithmic Probability and Combinatorics. Providence, Rhode Island: American Mathematical Society, 2010. http://dx.doi.org/10.1090/conm/520.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Melczer, Stephen. Algorithmic and Symbolic Combinatorics. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-67080-1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Can, Mahir, Zhenheng Li, Benjamin Steinberg, and Qiang Wang, eds. Algebraic Monoids, Group Embeddings, and Algebraic Combinatorics. New York, NY: Springer New York, 2014. http://dx.doi.org/10.1007/978-1-4939-0938-4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Pillwein, Veronika, and Carsten Schneider, eds. Algorithmic Combinatorics: Enumerative Combinatorics, Special Functions and Computer Algebra. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-44559-1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Klin, Mikhail, Gareth A. Jones, Aleksandar Jurišić, Mikhail Muzychuk, and Ilia Ponomarenko, eds. Algorithmic Algebraic Combinatorics and Gröbner Bases. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-01960-9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Algorithmic algebraic combinatorics and Gröbner bases. Heidelberg: Springer, 2009.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

Calude, Cristian S. Information and Randomness: An Algorithmic Perspective. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

Habib, Michel. Probabilistic Methods for Algorithmic Discrete Mathematics. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

Longueville, Mark. A Course in Topological Combinatorics. New York, NY: Springer New York, 2013.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

Linda, Pagli, and Steel Graham 1977-, eds. Mathematical and algorithmic foundations of the internet. Boca Raton, Fla: Chapman & Hall/CRC Press, 2011.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Algorithmic and combinatorics of monoids"

1

Li, Zhenheng, Zhuo Li, and You’an Cao. "Algebraic Monoids and Renner Monoids." In Algebraic Monoids, Group Embeddings, and Algebraic Combinatorics, 141–87. New York, NY: Springer New York, 2014. http://dx.doi.org/10.1007/978-1-4939-0938-4_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Henckell, Karsten, and Jean-Eric Pin. "Ordered Monoids and J-Trivial Monoids." In Algorithmic Problems in Groups and Semigroups, 121–37. Boston, MA: Birkhäuser Boston, 2000. http://dx.doi.org/10.1007/978-1-4612-1388-8_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Nešetřil, Jaroslav, and Patrice Ossona de Mendez. "Algorithmic Applications." In Algorithms and Combinatorics, 397–410. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-27875-4_18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Dress, A., O. Delgado Friedrichs, and D. Huson. "An Algorithmic Approach to Tilings." In Combinatorics Advances, 111–19. Boston, MA: Springer US, 1995. http://dx.doi.org/10.1007/978-1-4613-3554-2_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Melczer, Stephen. "Automated Analytic Combinatorics." In Algorithmic and Symbolic Combinatorics, 263–304. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-67080-1_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Brion, Michel. "On Algebraic Semigroups and Monoids." In Algebraic Monoids, Group Embeddings, and Algebraic Combinatorics, 1–54. New York, NY: Springer New York, 2014. http://dx.doi.org/10.1007/978-1-4939-0938-4_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Raymond, Jean-François, Pascal Tesson, and Denis Thérien. "Multiparty Communication Complexity of Finite Monoids." In Algorithmic Problems in Groups and Semigroups, 217–33. Boston, MA: Birkhäuser Boston, 2000. http://dx.doi.org/10.1007/978-1-4612-1388-8_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Molloy, Michael, and Bruce Reed. "Algorithmic Aspects of the Local Lemma." In Algorithms and Combinatorics, 295–313. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/978-3-642-04016-0_25.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Melczer, Stephen. "Introduction." In Algorithmic and Symbolic Combinatorics, 1–18. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-67080-1_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Melczer, Stephen. "Application: Lattice Paths, Revisited." In Algorithmic and Symbolic Combinatorics, 387–405. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-67080-1_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Algorithmic and combinatorics of monoids"

1

Mishna, Marni. "Algorithmic Approaches for Lattice Path Combinatorics." In ISSAC '17: International Symposium on Symbolic and Algebraic Computation. New York, NY, USA: ACM, 2017. http://dx.doi.org/10.1145/3087604.3087664.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Giotis, Ioannis, Lefteris Kirousis, Kostas I. Psaromiligkos, and Dimitrios M. Thilikos. "On the Algorithmic Lovász Local Lemma and Acyclic Edge Coloring." In 2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2014. http://dx.doi.org/10.1137/1.9781611973761.2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Bognar, Melinda. "From Intuition to Randomness: Combinatorics as Architectural Design Methodology in the Wave Function Collapse Algorithm." In Design Computation Input/Output 2021. Design Computation, 2021. http://dx.doi.org/10.47330/dcio.2021.zpdw5322.

Full text
Abstract:
Architectural design methods have doubtlessly changed due to the digital paradigm shift. The linear workflow of design turned to a loop and the level of human abstraction in each design phase are led by algorithmic computation. Facing this phenomenon is a puzzle for many professionals. Instead of designing the exact output of an architectural work digital allows to plan the method of creation with possibly similar but not necessarily identical results. This paper through the examination of the Wave Function Collapse algorithm highlights the ideological tensions compared to the traditional design process by showing how the human intuition can turn to machinic randomness.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Algorithmic and combinatorics of monoids' for particular source types:
Journal articles Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography