Thematische Bibliographien / Algorithmic and combinatorics of monoids

Inhaltsverzeichnis

  1. Zeitschriftenartikel
  2. Dissertationen
  3. Bücher
  4. Buchteile
  5. Konferenzberichte

Auswahl der wissenschaftlichen Literatur zum Thema „Algorithmic and combinatorics of monoids“

Autor: Grafiati
Veröffentlicht am 25. Mai 2024

Geben Sie eine Quelle nach APA, MLA, Chicago, Harvard und anderen Zitierweisen an

Wählen Sie eine Art der Quelle aus:

Machen Sie sich mit den Listen der aktuellen Artikel, Bücher, Dissertationen, Berichten und anderer wissenschaftlichen Quellen zum Thema "Algorithmic and combinatorics of monoids" bekannt.

Neben jedem Werk im Literaturverzeichnis ist die Option "Zur Bibliographie hinzufügen" verfügbar. Nutzen Sie sie, wird Ihre bibliographische Angabe des gewählten Werkes nach der nötigen Zitierweise (APA, MLA, Harvard, Chicago, Vancouver usw.) automatisch gestaltet.

Sie können auch den vollen Text der wissenschaftlichen Publikation im PDF-Format herunterladen und eine Online-Annotation der Arbeit lesen, wenn die relevanten Parameter in den Metadaten verfügbar sind.

Zeitschriftenartikel zum Thema "Algorithmic and combinatorics of monoids"

1

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

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
2

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

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
3

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

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
4

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

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
5

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

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
6

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

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
7

Okniński, Jan, und Magdalena Wiertel. „Combinatorics and structure of Hecke–Kiselman algebras“. Communications in Contemporary Mathematics 22, Nr. 07 (15.06.2020): 2050022. http://dx.doi.org/10.1142/s0219199720500224.

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
8

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

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
9

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

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
10

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

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
Mehr Quellen

Dissertationen zum Thema "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.

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
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.

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
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.

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
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.

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
5

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

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
6

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

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
7

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

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
8

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

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
9

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

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
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.

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen

Bücher zum Thema "Algorithmic and combinatorics of monoids"

1

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

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
2

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

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
3

Can, Mahir, Zhenheng Li, Benjamin Steinberg und Qiang Wang, Hrsg. 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.

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
4

Pillwein, Veronika, und Carsten Schneider, Hrsg. 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.

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
5

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

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
6

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

Den vollen Inhalt der Quelle finden
APA, Harvard, Vancouver, ISO und andere Zitierweisen
7

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

Den vollen Inhalt der Quelle finden
APA, Harvard, Vancouver, ISO und andere Zitierweisen
8

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

Den vollen Inhalt der Quelle finden
APA, Harvard, Vancouver, ISO und andere Zitierweisen
9

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

Den vollen Inhalt der Quelle finden
APA, Harvard, Vancouver, ISO und andere Zitierweisen
10

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

Den vollen Inhalt der Quelle finden
APA, Harvard, Vancouver, ISO und andere Zitierweisen
Mehr Quellen

Buchteile zum Thema "Algorithmic and combinatorics of monoids"

1

Li, Zhenheng, Zhuo Li und 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.

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
2

Henckell, Karsten, und 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.

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
3

Nešetřil, Jaroslav, und 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.

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
4

Dress, A., O. Delgado Friedrichs und 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.

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
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.

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
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.

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
7

Raymond, Jean-François, Pascal Tesson und 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.

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
8

Molloy, Michael, und 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.

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
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.

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
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.

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen

Konferenzberichte zum Thema "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.

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
2

Giotis, Ioannis, Lefteris Kirousis, Kostas I. Psaromiligkos und 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.

Der volle Inhalt der Quelle
APA, Harvard, Vancouver, ISO und andere Zitierweisen
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.

Der volle Inhalt der Quelle
Annotation:
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 und andere Zitierweisen
Die Auswahlen zum Thema "Algorithmic and combinatorics of monoids" für konkrete Quellenarten können Sie auch interessieren:
Zeitschriftenartikel Bücher
Wir bieten Rabatte auf alle Premium-Pläne für Autoren, deren Werke in thematische Literatursammlungen aufgenommen wurden. Kontaktieren Sie uns, um einen einzigartigen Promo-Code zu erhalten!

Zur Bibliographie