To see the other types of publications on this topic, follow the link: Monoid.
Dissertations / Theses on the topic 'Monoid'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Monoid.'
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.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Render, Elaine. "Rational monoid and semigroup automata." Thesis, University of Manchester, 2010. https://www.research.manchester.ac.uk/portal/en/theses/rational-monoid-and-semigroup-automata(0aff0c17-b6f9-4bc8-95d1-ff98da059d42).html.
Full textAbstract:
We consider a natural extension to the definition of M-automata which allows the automaton to make use of more of the structure of the monoid M, and by removing the reliance on an identity element, allows the definition of S-automata for S an arbitrary semigroup. In the case of monoids, the resulting automata are equivalent to valence automata with rational target sets which arise in the theory of regulated rewriting. We focus on the polycyclic monoids, and show that for polycyclic monoids of rank 2 or more they accept precisely the context-free languages. The case of the bicyclic monoid is also considered. In the process we prove a number of interesting results about rational subsets in polycyclic monoids; as a consequence we prove the decidability of the rational subset membership problem, and the closure of the class of rational subsets under intersection and complement. In the case of semigroups, we consider the important class of completely simple and completely 0-simple semigroups, obtaining a complete characterisation of the classes of languages corresponding to such semigroups, in terms of their maximal subgroups. In the process, we obtain a number of interesting results about rational subsets of Rees matrix semigroups.
2
Cevik, Ahmet Sinan. "Minimality of group and monoid presentations." Thesis, University of Glasgow, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.284692.
Full text
3
Salt, Brittney M. "MONOID RINGS AND STRONGLY TWO-GENERATED IDEALS." CSUSB ScholarWorks, 2014. https://scholarworks.lib.csusb.edu/etd/31.
Full textAbstract:
This paper determines whether monoid rings with the two-generator property have the strong two-generator property. Dedekind domains have both the two-generator and strong two-generator properties. How common is this? Two cases are considered here: the zero-dimensional case and the one-dimensional case for monoid rings. Each case is looked at to determine if monoid rings that are not PIRs but are two-generated have the strong two-generator property. Full results are given in the zero-dimensional case, however only partial results have been found for the one-dimensional case.
4
Lima, Lucinda Maria de Carvalho. "The local automorphism monoid of an independence algebra." Thesis, University of York, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.358341.
Full text
5
Catarino, Paula Maria Machado Cruz. "The monoid of orientation-preserving mappings on a chain." Thesis, University of Essex, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.266839.
Full text
6
Oltmanns, Helga. "Homological classification of monoids by projectivities of right acts." [S.l. : s.n.], 2000. http://deposit.ddb.de/cgi-bin/dokserv?idn=960378634.
Full text
7
Ramasu, Pako. "Internal monoid actions in a cartesian closed category and higher-dimensional group automorphisms." Doctoral thesis, University of Cape Town, 2015. http://hdl.handle.net/11427/20248.
Full textAbstract:
The notion of cat¹-group which was introduced by Loday is equivalent to the notions of crossed module and of internal category in the category of groups. This notion of cat¹-groups and their morphisms admits natural generalization to catⁿ-groups, which give rise to n-fold categories in the category of groups. There is also a characterization of catⁿ-groups in terms of crossed n-cubes which was given by Ellis and Steiner. The category Catⁿ (Groups) of internal n-fold categories in the category of groups is a cartesian closed category, however given an object X in Catⁿ (Groups), calculating corresponding action representing object Aut (X) directly would require an enormous calculations. The main purpose of the thesis is to describe that object avoiding such calculations as much as possible. The main tool used in the thesis, apart from the theory of cartesian closed categories, is Loday's theory of catⁿ-groups. We de ne a catⁿ-group X as an additive Mₙ-group X , and then construct the corresponding Aut (X), where Mₙ is a monoid. Since the category of catⁿ-groups is equivalent to Catⁿ (Groups) and since the cartesian closed category Sets Mₙ of Mₙ-sets is much easier to handle than the cartesian closed category of n-fold categories, we shall work just with catⁿ-groups. To assert that, Aut (X) is an action representing object in Sets Mₙ , is to as- sert that, there is a canonical bijection between B-actions of catⁿ-group B on X and the internal group homomorphism B --> Aut (X). Thus, we confirm the construction of Aut (X) by establishing that bijection. Finally, as one of the results of this work, we give the comparison between our cat¹-group Aut (X) and Norrie's actor crossed module (D (G;Z) ;Aut (Z;G;p) w) of a crossed module (Z;G;p) in dimension one.
8
Duchamp, Gérard. "Algorithmes sur les polynomes en variables non commutatives." Paris 7, 1987. http://www.theses.fr/1987PA077069.
Full textAbstract:
Etude des monoides libres et de leurs algebres. Presentation de nouvelles caracterisations des bisections reconnaissables; de la caracterisation des mots pouvant appartenir au support d'un polynome de lie et de l'etude de quelques proprietes algebriques de polynomes en variables partiallement commutatives. Etude du treillis des congruences regulieres sur le monoide bicyclique
9
Tesson, Emilie. "Un hybride du groupe de Thompson F et du groupe de tresses B°°." Thesis, Normandie, 2018. http://www.theses.fr/2018NORMC212/document.
Full textAbstract:
Nous étudions un certain monoïde défini par une présentation, notée P, qui est un hybride de celles du monoïde de tresses infinies et du monoïde de Thompson. Pour cela, nous utilisons plusieurs approches. On décrit d’abord un système de réécriture convergent pour la présentation P, ce qui fournit en particulier une solution au problème de mots de P et rapproche le monoïde hybride du monoïde de Thompson. Puis, suivant le modèle du monoïde de tresses, on utilise la méthode du retournement de facteur pour analyser la relation de divisibilité à gauche, et montrer en particulier que le monoïde hybride admet la simplification et des ppcm à droite conditionnels. Ensuite, on étudie la combinatoire de Garside de l'hybride: pour chaque entier n, on introduit un élément ∆(n) comme ppcm à droite des (n−1) premiers atomes, et on étudie les diviseurs à gauche des éléments ∆(n), appelés éléments simples. Les principaux résultats sont les dénombrement des diviseurs à gauche de ∆(n) et la détermination effective des formes normales des éléments simples. On termine en construisant des représentations du monoïde hybride dans divers monoïdes, en particulier une représentation dans des matrices à coefficients polynômes de Laurent dont on conjecture qu’elle est fidèle<br>We study a certain monoid specified by a presentation, denoted P, that is a hybrid of the classical presentation of the infinite braid monoid and of the presentation of Thompson’s monoid. To this end, we use several approaches. First, we describe a convergent rewrite system for P, which provides in particular a solution to the word problem, and makes the hybrid monoid reminiscent of Thompson’s monoid. Next, on the shape of the braid monoid, we use the factor reversing method to analyze the divisibility relation, and show in particular that the hybrid monoid admits cancellation and conditional right lcms. Then, we study Garside combinatorics of the hybrid: for every integer n, we introduce an element ∆(n) as the right lcm of the first (n−1) atoms, and one investigates the left divisors of the elements ∆(n), called simple elements. The main results are a counting of the left divisors of ∆(n) and a characterization of the normal forms of simple elements. We conclude with the construction of several representations of the hybrid monoid in various monoids, in particular a representation in a monoid of matrices whose entries are Laurent polynomials, which we conjecture could be faithful
10
East, James Phillip Hinton. "On Monoids Related to Braid Groups and Transformation Semigroups." School of Mathematics and Statistics, 2006. http://hdl.handle.net/2123/2438.
Full text
11
East, James Phillip Hinton. "On Monoids Related to Braid Groups and Transformation Semigroups." Thesis, The University of Sydney, 2005. http://hdl.handle.net/2123/2438.
Full text
12
Lohrey, Markus. "Computational and logical aspects of infinite monoids." [S.l. : s.n.], 2003. http://www.bsz-bw.de/cgi-bin/xvms.cgi?SWB10720633.
Full text
13
Bertol, Michael W. "Effiziente Normalform-Algorithmen für Ersetzungssysteme über frei partiell kommutativen Monoiden." [S.l. : s.n.], 1996. http://www.bsz-bw.de/cgi-bin/xvms.cgi?SWB5222391.
Full text
14
Kufleitner, Manfred. "Logical fragments for Mazurkiewicz traces expressive power and algebraic characterizations /." [S.l. : s.n.], 2006. http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-27812.
Full text
15
Bourne, Thomas. "Counting subwords and other results related to the generalised star-height problem for regular languages." Thesis, University of St Andrews, 2017. http://hdl.handle.net/10023/12024.
Full textAbstract:
The Generalised Star-Height Problem is an open question in the field of formal language theory that concerns a measure of complexity on the class of regular languages; specifically, it asks whether or not there exists an algorithm to determine the generalised star-height of a given regular language. Rather surprisingly, it is not yet known whether there exists a regular language of generalised star-height greater than one. Motivated by a theorem of Thérien, we first take a combinatorial approach to the problem and consider the languages in which every word features a fixed contiguous subword an exact number of times. We show that these languages are all of generalised star-height zero. Similarly, we consider the languages in which every word features a fixed contiguous subword a prescribed number of times modulo a fixed number and show that these languages are all of generalised star-height at most one. Using these combinatorial results, we initiate work on identifying the generalised star-height of the languages that are recognised by finite semigroups. To do this, we establish the generalised star-height of languages recognised by Rees zero-matrix semigroups over nilpotent groups of classes zero and one before considering Rees zero-matrix semigroups over monogenic semigroups. Finally, we explore the generalised star-height of languages recognised by finite groups of a given order. We do this through the use of finite state automata and 'count arrows' to examine semidirect products of the form A x Zr where A is an abelian group and Zr is the cyclic group of order r.
16
Perez, Gavilan Torres Jacinta [Verfasser], Peter [Akademischer Betreuer] Littelmann, and Alexander [Akademischer Betreuer] Alldridge. "The symplectic plactic monoid, words, MV cycles, and non-Levi branchings / Jacinta Perez Gavilan Torres. Gutachter: Peter Littelmann ; Alexander Alldridge." Köln : Universitäts- und Stadtbibliothek Köln, 2015. http://d-nb.info/1082030481/34.
Full text
17
Owusu-Mensah, Isaac. "Algebraic Structures on the Set of all Binary Operations over a Fixed Set." Ohio University / OhioLINK, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1584490788584639.
Full text
18
Perone, Marco. "Direct sum decompositions and weak Krull-Schmidt Theorems." Doctoral thesis, Università degli studi di Padova, 2011. http://hdl.handle.net/11577/3427427.
Full textAbstract:
In this thesis we discuss the behaviour of direct sum decomposition in additive categories and in particular in categories of modules.
In the first part of the thesis, we investigate the ring theoretical properties that play a main role in the theory of factorization in additive categories, like the exchange property, semilocality and Goldie dimension. We stress the importance of the latter and we investigate with care the infinite case of the dual Goldie dimension of rings.
In the rest of the thesis, we use a more categorical approach, studying the behaviour of direct sum decomposition in additive categories. Given an additive category C, its skeleton V(C) has the structure of a commutative monoid under the operation of direct sum, and all the information about the regularity of the direct sum decomposition in the category C are traceable from the monoid V(C). We study classes of categories where the direct sum decomposition behaves quite regularly; mainly we restrict to categories C whose monoid V(C) is a Krull monoid, underlining the prominent role played by semilocal endomorphism rings. We analyze the peculiar behaviour of direct sum decomposition in some categories of modules, where the uniqueness of the decomposition is obtained up to two permutations, and we notice how this phenomenon is due to the presence of endomorphism rings of type two. In the last chapter we investigate what happens when we pass from finite direct sum of indecomposable objects to infinite direct sums, and we develop the setting for the phenomena we studied in the finite case to appear, both at a monoid theoretical and at a categorical level.<br>In questa tesi discutiamo il comportamento della decomposizione in somma diretta in categorie additive e in particolare in categorie di moduli.
Nella prima parte della tesi, investighiamo le proprietà degli anelli che giocano un ruolo prominente nella teoria della fattorizzazione nelle categorie additive, come per esempio la proprietà di scambio, la semilocalità e la dimensione di Goldie. Vogliamo sottolineare l'importanza di quest'ultima e investighiamo con attenzione il caso infinito della dimensione duale di Goldie di un anello.
Nel resto della tesi, utilizziamo un approccio più categoriale, studiando il comportamento della decomposizione in somma diretta nelle categorie additive. Data una categoria additiva C, il suo scheletro V(C) ha la struttura di un monoide commutativo rispetto all'operazione di somma diretta, e tutte le informazioni riguardo la regolarità della decomposizione in somma diretta nella categoria C sono rintracciabili attraverso il monoide V(C). Studiamo classi di categorie in cui la decomposizione in somma diretta assume un comportamento abbastanza regolare; principalemente ci restringiamo a categorie C il cui monoide V(C) è un monoide di Krull, evidenziando il ruolo prominente occupato da parte degli anelli degli endomorfismi semilocali. Analizziamo il comportamento peculiare della decomposizione in somma diretta in alcune categorie di moduli, dove l'unicità della decomposizione è garantita a meno di due permutazioni, e notiamo come questo fenomeno sia dovuto alla presenza di anelli degli endomorfismi di tipo due. Nell'ultimo capitolo investighiamo cosa succede quando passiamo da somme dirette finite di oggetti indecomponibili a somme dirette infinite, e sviluppiamo l'ambiente in cui i fenomeni studiati precedentemente nel caso finito si manifestano, sia ad un livello di teoria dei monodi sia ad un livello categoriale.
19
Marseglia, Stefano. "Isomorphism classes of abelian varieties over finite fields." Licentiate thesis, Stockholms universitet, Matematiska institutionen, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-130316.
Full textAbstract:
Deligne and Howe described polarized abelian varieties over finite fields in terms of finitely generated free Z-modules satisfying a list of easy to state axioms. In this thesis we address the problem of developing an effective algorithm to compute isomorphism classes of (principally) polarized abelian varieties over a finite field, together with their automorphism groups. Performing such computations requires the knowledge of the ideal classes (both invertible and non-invertible) of certain orders in number fields. Hence we describe a method to compute the ideal class monoid of an order and we produce concrete computations in dimension 2, 3 and 4.
20
Kuber, Amit Shekhar. "K-theory of theories of modules and algebraic varieties." Thesis, University of Manchester, 2014. https://www.research.manchester.ac.uk/portal/en/theses/ktheory-of-theories-of-modules-and-algebraic-varieties(5d4387d5-df36-455a-a09d-922d67b0827e).html.
Full text
21
Calladine, Pierre. "Equations et systèmes de réécritures dans le monoïde libre : une approche commune." Poitiers, 1989. http://www.theses.fr/1989POIT2254.
Full textAbstract:
Une structure originale, appelee codecoupage sur une famille de mots, permet de definir un ensemble de mots du monoide libre engendre par un alphabet a par la donnee de couples d'occurrences de facteurs egaux dans ces mots. Cette notion permet une demonstration nouvelle de l'existence et l'unicite d'une solution principale divisant une solution d'un systeme d'equations dans le monoide. Le concept de codecoupage permet aussi de definir une notion d'isomorphisme, combinatoire entre systemes de reecritures dans le monoide
22
Krob, Daniel. "Expressions k-rationnelles." Paris 7, 1988. http://www.theses.fr/1988PA077088.
Full textAbstract:
Construction d'une theorie des expressions rationnelles sur un semi anneau k quelconque. La theorie est ensuite generalisee aux identites matricielles en montrant que certaines axiomes classiques entrainent leur version matricielle. Il est aussi etabli que l'etoile formelle d'une matrice se definit de maniere unique, module les axiomes classiques. Un calcul differentiel sur les expressions k-rationnelles est etudie, en montrant comment l'on peut deduire des identites derivees. Dans une derniere partie, les codes intervenant dans une factorisation finie du monoide libre sont etudies
23
ABBADINI, MARCO. "ON THE AXIOMATISABILITY OF THE DUAL OF COMPACT ORDERED SPACES." Doctoral thesis, Università degli Studi di Milano, 2021. http://hdl.handle.net/2434/812809.
Full textAbstract:
We prove that the category of Nachbin's compact ordered spaces and order-preserving continuous maps between them is dually equivalent to a variety of algebras, with operations of at most countable arity. Furthermore, we show that the countable bound on the arity is the best possible: the category of compact ordered spaces is not dually equivalent to any variety of finitary algebras. Indeed, the following stronger results hold: the category of compact ordered spaces is not dually equivalent to (i) any finitely accessible category, (ii) any first-order definable class of structures, (iii) any class of finitary algebras closed under products and subalgebras. An explicit equational axiomatisation of the dual of the category of compact ordered spaces is obtained; in fact, we provide a finite one, meaning that our description uses only finitely many function symbols and finitely many equational axioms. In preparation for the latter result, we establish a generalisation of a celebrated theorem by D. Mundici: our result asserts that the category of unital commutative distributive lattice-ordered monoids is equivalent to the category of what we call MV-monoidal algebras. Our proof is independent of Mundici's theorem.
24
Powell, Mark Andrew. "Second order algebraic knot concordance group." Thesis, University of Edinburgh, 2011. http://hdl.handle.net/1842/5030.
Full textAbstract:
Let Knots be the abelian monoid of isotopy classes of knots S1 ⊂ S3 under connected sum, and let C be the topological knot concordance group of knots modulo slice knots. Cochran-Orr-Teichner [COT03] defined a filtration of C: C ⊃ F(0) ⊃ F(0.5) ⊃ F(1) ⊃ F(1.5) ⊃ F(2) ⊃ . . .The quotient C/F(0.5) is isomorphic to Levine’s algebraic concordance group AC1 [Lev69]; F(0.5) is the algebraically slice knots. The quotient C/F(1.5) contains all metabelian concordance obstructions. The Cochran-Orr-Teichner (1.5)-level two stage obstructions map the concordance class of a knot to a pointed set (COT (C/1.5),U). We define an abelian monoid of chain complexes P, with a monoid homomorphism Knots → P. We then define an algebraic concordance equivalence relation on P and therefore a group AC2 := P/ ~, our second order algebraic knot concordance group. The results of this thesis can be summarised in the following diagram: . That is, we define a group homomorphism C → AC2 which factors through C/F(1.5). We can extract the two stage Cochran-Orr-Teichner obstruction theory from AC2: the dotted arrows are morphisms of pointed sets. Our second order algebraic knot concordance group AC2 is a single stage obstruction group.
25
Wilding, David. "Linear algebra over semirings." Thesis, University of Manchester, 2015. https://www.research.manchester.ac.uk/portal/en/theses/linear-algebra-over-semirings(1dfe7143-9341-4dd1-a0d1-ab976628442d).html.
Full textAbstract:
Motivated by results of linear algebra over fields, rings and tropical semirings, we present a systematic way to understand the behaviour of matrices with entries in an arbitrary semiring. We focus on three closely related problems concerning the row and column spaces of matrices. This allows us to isolate and extract common properties that hold for different reasons over different semirings, yet also lets us identify which features of linear algebra are specific to particular types of semiring. For instance, the row and column spaces of a matrix over a field are isomorphic to each others' duals, as well as to each other, but over a tropical semiring only the first of these properties holds in general (this in itself is a surprising fact). Instead of being isomorphic, the row space and column space of a tropical matrix are anti-isomorphic in a certain order-theoretic and algebraic sense. The first problem is to describe the kernels of the row and column spaces of a given matrix. These equivalence relations generalise the orthogonal complement of a set of vectors, and the nature of their equivalence classes is entirely dependent upon the kind of semiring in question. The second, Hahn-Banach type, problem is to decide which linear functionals on row and column spaces of matrices have a linear extension. If they all do, the underlying semiring is called exact, and in this case the row and column spaces of any matrix are isomorphic to each others' duals. The final problem is to explain the connection between the row space and column space of each matrix. Our notion of a conjugation on a semiring accounts for the different possibilities in a unified manner, as it guarantees the existence of bijections between row and column spaces and lets us focus on the peculiarities of those bijections. Our main original contribution is the systematic approach described above, but along the way we establish several new results about exactness of semirings. We give sufficient conditions for a subsemiring of an exact semiring to inherit exactness, and we apply these conditions to show that exactness transfers to finite group semirings. We also show that every Boolean ring is exact. This result is interesting because it allows us to construct a ring which is exact (also known as FP-injective) but not self-injective. Finally, we consider exactness for residuated lattices, showing that every involutive residuated lattice is exact. We end by showing that the residuated lattice of subsets of a finite monoid is exact if and only if the monoid is a group.
26
Golchin, Akbar. "Homological classification of monoids." Thesis, University of Southampton, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.243655.
Full text
27
Rannou, Pierre. "Réécriture de diagrammes et de Sigma-diagrammes." Thesis, Aix-Marseille, 2013. http://www.theses.fr/2013AIXM4063.
Full textAbstract:
Peaks andThe main subject of this thesis is diagram rewriting.This is a generalisation to dimension~$2$ of word rewriting (in dimension~$1$). In a first time, we give the first convergent diagrammatic presentation of the PRO of linear maps in arbitrary field. Then we study the convergent diagrammatic presentation of matrix of isometries of $RR^n$. We focus especially on a rule similar to the Yang-Baxter equation, described by a certain map $h$. We use the confluence of critical the parametric diagrams, To study the algebraic properties of $h$, Finally, we present the $Sigma$-diagrams, an alternative approach for calculation in bialgebras. We illustrate this approach with examples. The last two chapters have been already published: Diagram rewriting for orthogonal matrices: a study of critical peaks, avec Yves Lafont, Lecture Notes in Computer Science 5117, p. 232-245, 2008 Properties of co-operations: diagrammatic proofs, Mathematical Structures in Computer Science 22(6), p. 970-986, 2012<br>The main subject of this thesis is diagram rewriting.This is a generalisation to dimension~$2$ of word rewriting (in dimension~$1$). In a first time, we give the first convergent diagrammatic presentation of the PRO of linear maps in arbitrary field. Then we study the convergent diagrammatic presentation of matrix of isometries of $RR^n$. We focus especially on a rule similar to the Yang-Baxter equation, described by a certain map $h$. We use the confluence of criticalthe parametric diagrams, To study the algebraic properties of $h$, Finally, we present the $Sigma$-diagrams, an alternative approach for calculation in bialgebras. We illustrate this approach with examples. The last two chapters have been already published: Diagram rewriting for orthogonal matrices: a study of critical peaks, avec Yves Lafont, Lecture Notes in Computer Science 5117, p. 232-245, 2008 Properties of co-operations: diagrammatic proofs, Mathematical Structures in Computer Science 22(6), p. 970-986, 2012
28
Gohon, Philippe. "Automates avec coût et reconnaissabilité dans les monoïdes libres commutatifs." Rouen, 1986. http://www.theses.fr/1986ROUES009.
Full textAbstract:
Etude des automates munis d'une fonction de coût sur un alphabet à une seule lettre : calcul de la borne optimale. Etude des monoïdes libres commutatifs finiment engendrés, des représentations des parties rationnelles. Preuve de la décidabilité de savoir si une partie rationnelle est limitée
29
Pecuchet, Jean-Pierre. "Automates boustrophédons : langages reconnaissables de mots infinis et variétés de semigroupes." Rouen, 1986. http://www.theses.fr/1986ROUES005.
Full textAbstract:
La 1ère partie traite des automates boustrophédons, du semi-groupe de Birget et du monoïde inversif libre. La 2ème partie étudie le comportement infini d'un automate boustrophédon, la 3ème partie est consacrée aux variétés de semi-groupes et aux mots infinis. La 4ème partie poursuit la classification des langages rationnels de mots infinis à l'aide des variétés des semi-groupes
30
Beaudry, Martin. "Membership testing in transformation monoids." Thesis, McGill University, 1987. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=75773.
Full textAbstract:
Given a finite set X of states, a finite set of transformations of X (generators), and another transformation f of X, we analyze the complexity of the membership problem, which consists in deciding whether f can be obtained by composition of the generators. This problem is studied for various classes (pseudovarieties) of monoids. It is shown that the complexity is NP-hard for monoids of threshold 2 or more, and NP-complete in commutative, J- and R-trivial monoids. For idempotent monoids (aperiodic of threshold one), the problem is NP-complete in the general case; subcases are analyzed, and a largest class of aperiodic monoids is identified for which the problem is in FL, as well as a largest class for which the problem is not NP-hard.<br>The problem which consists in characterizing an idempotent monoid is also addressed: given a set of transformations, it can be decided in NC$ sp2$ whether the monoid they generate is idempotent. Similar tests are given for three subclasses of idempotent monoids: R$ sb1$, L$ sb1$, and N$ sb3$; in all three cases, the complexity is NC$ sp1$.<br>A sequential upper bound is also given for each of the parallel complexities given above.
31
Hindlycke, Christoffer. "Irreducible representations of finite monoids." Thesis, Uppsala universitet, Algebra och geometri, 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-380588.
Full text
32
Jones, David G. "Polycyclic monoids and their generalisations." Thesis, Heriot-Watt University, 2011. http://hdl.handle.net/10399/2473.
Full text
33
Bailey, Alexander. "Covers of acts over monoids." Thesis, University of Southampton, 2013. https://eprints.soton.ac.uk/363273/.
Full textAbstract:
Since they were first defined in the 1950's, projective covers (the dual of injective envelopes) have proved to be an important tool in module theory, and indeed in many other areas of abstract algebra. An attempt to generalise the concept led to the introduction of covers with respect to other classes of modules, for example, injective covers, torsion-free covers and at covers. The at cover conjecture (now a Theorem) is of particular importance, it says that every module over every ring has a at cover. This has led to surprising results in cohomological studies of certain categories. Given a general class of objects X, an X-cover of an object A can be thought of a the `best approximation' of A by an object from X. In a certain sense, it behaves like an adjoint to the inclusion functor. In this thesis we attempt to initiate the study of di�erent types of covers for the category of acts over a monoid. We give some necessary and sufficient conditions for the existence of X covers for a general class X of acts, and apply these results to specific classes. Some results include, every S act has a strongly at cover if S satisfies Condition (A), every S-act has a torsion free cover if S is cancellative, and every S-act has a divisible cover if and only if S has a divisible ideal. We also consider the important concept of purity for the category of acts. Giving some new characterisations and results for pure monomorphisms and pure epimorphisms.
34
Wannenburg, Johann Joubert. "Varieties of De Morgan Monoids." Thesis, University of Pretoria, 2020. http://hdl.handle.net/2263/75178.
Full textAbstract:
De Morgan monoids are algebraic structures that model certain non-classical logics. The variety DMM of all De Morgan monoids models the relevance logic Rt (so-named because it blocks the derivation of true conclusions from irrelevant premises). The so-called subvarieties and subquasivarieties of DMM model the strengthenings of Rt by new logical axioms, or new inference rules, respectively. Meta-logical problems concerning these stronger systems amount to structural problems about (classes of) De Morgan monoids, and the methods of universal algebra can be exploited to solve them. Until now, this strategy was under-developed in the case of Rt and DMM.
The thesis contributes in several ways to the filling of this gap. First, a new structure theorem for irreducible De Morgan monoids is proved; it leads to representation theorems for the algebras in several interesting subvarieties of DMM. These in turn help us to analyse the lower part of the lattice of all subvarieties of DMM. This lattice has four atoms, i.e., DMM has just four minimal subvarieties. We describe in detail the second layer of this lattice, i.e., the covers of the four atoms. Within certain subvarieties of DMM, our description amounts to an explicit list of all the covers. We also prove that there are just 68 minimal quasivarieties of De Morgan monoids.
Thereafter, we use these insights to identify strengthenings of Rt with certain desirable meta-logical features. In each case, we work with the algebraic counterpart of a meta-logical property. For example, we identify precisely the varieties of De Morgan monoids having the joint embedding property (any two nontrivial members both embed into some third member), and we establish convenient sufficient conditions for epimorphisms to be surjective in a subvariety of DMM. The joint embedding property means that the corresponding logic is determined by a single set of truth tables. Epimorphisms are related to 'implicit definitions'. (For instance, in a ring, the multiplicative inverse of an element is implicitly defined, because it is either uniquely determined or non-existent.) The logical meaning of epimorphism-surjectivity is, roughly speaking, that suitable implicit definitions can be made explicit in the corresponding logical syntax.<br>Thesis (PhD)--University of Pretoria, 2020.<br>DST-NRF Centre of Excellence in Mathematical and Statistical Sciences (CoE-MaSS)<br>Mathematics and Applied Mathematics<br>PhD<br>Unrestricted
35
Burns, Brenda D. "The Staircase Decomposition for Reductive Monoids." NCSU, 2002. http://www.lib.ncsu.edu/theses/available/etd-20020422-102254.
Full textAbstract:
<p>Burns, Brenda Darlene. The Staircase Decomposition for Reductive Monoids. (Under the direction of Mohan Putcha.) The purpose of the research has been to develop a decomposition for the J-classes of a reductive monoid. The reductive monoid M(K) isconsidered first. A J-class in M(K) consists ofelements of the same rank. Lower and upper staircase matricesare defined and used to decompose a matrix x of rank r into theproduct of a lower staircase matrix, a matrix with a rank rpermutation matrix in the upper left hand corner, and an upperstaircase matrix, each of which is of rank r. The choice ofpermutation matrix is shown to be unique. The primary submatrix of a matrixis defined. The unique permutation matrix from the decompositionabove is seen to be the unique permutation matrix from Bruhat'sdecomposition for the primary submatrix. All idempotent elementsand regular J-classes of the lower and upper staircasematrices are determined. A decomposition for the upper and lowerstaircase matrices is given as well.The above results are then generalized to an arbitrary reductivemonoid by first determining the analogue of the components forthe decomposition above. Then the decomposition above is shown tobe valid for each J-class of a reductive monoid. Theanalogues of the upper and lower staircase matrices are shown tobe semigroups and all idempotent elements and regularJ-classes are determined. A decomposition for eachof them is discussed.<P>
36
Williamson, Helen. "Immersions of complexes and inverse monoids." Thesis, University of York, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.261082.
Full text
37
Hollings, Christopher David. "Partial actions of semigroups and monoids." Thesis, University of York, 2007. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.440689.
Full text
38
Cutting, Andrew. "Todd-Coxeter methods for inverse monoids." Thesis, University of St Andrews, 2001. http://hdl.handle.net/10023/15052.
Full textAbstract:
Let P be the inverse monoid presentation (X|U) for the inverse monoid M, let π be the set of generators for a right congruence on M and let u Є M. Using the work of J. Stephen [15], the current work demonstrates a coset enumeration technique for the R-class Ru similar to the coset enumeration algorithm developed by J. A. Todd and H. S. M. Coxeter for groups. Furthermore it is demonstrated how to test whether Ru = Rv, for u, v Є M and so a technique for enumerating inverse monoids is described. This technique is generalised to enumerate the H-classes of M. The algorithms have been implemented in GAP 3.4.4 [25], and have been used to analyse some examples given in Chapter 6. The thesis concludes by a related discussion of normal forms and automaticity of free inverse semigroups.
39
Ramos, Sandra Isabel Diogo. "O monoide bicíclico: subsemigrupos e generalizações." Master's thesis, Universidade de Aveiro, 2008. http://hdl.handle.net/10773/2904.
Full textAbstract:
Mestrado em Matemática - Ensino<br>Esta dissertação consiste num trabalho de recolha bibliográfica e síntese sobre
o monoide bicíclico, B, propriedades, subsemigrupos, e generalizações. Iniciase
o trabalho com uma breve introdução à teoria de semigrupos em geral, com
ênfase para os conceitos necessários aos restantes capítulos. Definimos
monoide bicíclico e apresentamos algumas propriedades notáveis do mesmo,
fazemos a descrição de todos os subsemigrupos de B, que utilizamos para
estabelecer diversas propriedades destes subsemigrupos. Estudamos apenas
em detalhe uma generalização e referimos outras. Foram incluídos resultados
recentes, nomeadamente sobre os subsemigrupos de B.<br>This thesis consists of a work of bibliographical selection and synthesis around
the bicyclic monoid, B, its properties, subsemigroups, and generalizations. The
thesis begins with a brief introduction to the theory of semigroups with
emphasis to the required concepts for the remaining chapters. We define the
bicyclic monoid and present some of its notable properties. Then we present
the description of all the subsemigroups of B, which we use to establish several
properties of these subsemigroups. We study one generalization in detail and
we briefly refer other generalizations. This work includes some recent results,
particularly on subsemigroups of B.
40
Duboc, Christine. "Commutations dans les monoïdes libres : un cadre théorique pour l'étude du parallélisme." Rouen, 1986. http://www.theses.fr/1986ROUES003.
Full text
41
Li, Zhuo. "Orbit structure of finite and reductive monoids." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/nq21301.pdf.
Full text
42
Smith, Eric R. "Right congruences on inverse Bruck-Reilly monoids." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/nq21316.pdf.
Full text
43
ArauÌjo, João Jorge Ribeiro Soares Gonçalves de. "Aspects of endomorphism monoids of independence algebras." Thesis, University of York, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.274496.
Full text
44
Hage, Nohra. "Study of plactic monoids by rewriting methods." Thesis, Lyon, 2016. http://www.theses.fr/2016LYSES065/document.
Full textAbstract:
Cette thèse est consacrée à l’étude des monoïdes plaxiques par une nouvelle approche utilisant des méthodes issues de la réécriture. Ces méthodes sont appliquées à des présentations de monoïdes plaxiques décrites en termes de tableaux de Young, de bases cristallines de Kashiwara et de modèle des chemins de Littelmann. On étudie le problème des syzygies pour la présentation de Knuth des monoïdes plaxiques. En utilisant la procédure de complétion homotopique basée sur les procédures de complétion de Squier et de Knuth–Bendix, on construit des présentations cohérentes de monoïdes plaxiques de type A. Une telle présentation cohérente étend la notion de présentation convergente d’un monoïde par une famille génératrice de syzygies, décrivant toutes les relations entre les relations. On explicite une présentation cohérente finie des monoïdes plaxiques de type A avec les générateurs colonnes. Cependant, cette présentation n’est pas minimale dans le sens que plusieurs de ses générateurs sont superflus. En appliquant la procédure de réduction homotopique, on réduit cette présentation en une présentation cohérente finie qui étend la présentation de Knuth, donnantainsi toutes les syzygies des relations de Knuth. D’une manière plus générale, on étudie des présentations de monoïdes plaxiques généralisés du point de vue de la réécriture. On construit des présentations convergentes finies de ces monoïdes en utilisant les chemins de Littelmann. De plus, on étudie ces présentations pour le type C en termes de bases cristallines de Kashiwara. En introduisant les générateurs colonnes admissibles, on construit une présentation convergente finie du monoïde plaxique de type C avec des relations explicites. Cette approche nous permettrait d’étudier le problème des syzygies des présentations de monoïdes plaxiques en tout type<br>This thesis focuses on the study of plactic monoids by a new approach using methods issued from rewriting theory. These methods are applied on presentations of plactic monoids given in terms of Young tableaux, Kashiwara’s crystal bases and Littelmann path model. We study the syzygy problem for the Knuth presentation of the plactic monoids. Using the homotopical completion procedure that extends Squier’s and Knuth–Bendix’s completions procedure, we construct coherent presentations of plactic monoids of type A. Such a coherent presentation extends the notion of a presentation of a monoid by a family of generating syzygies, taking into account all the relations among the relations. We make explicit a finite coherent presentation of plactic monoids of type A with the column generators. However, this presentation is not minimal in the sense that many of its generators are superfluous. After applying the homotopical reduction procedure on this presentation, we reduce it to a finite coherent one that extends the Knuth presentation, giving then all the syzygies of the Knuth relations. More generally, we deal with presentations of plactic monoids of any type from the rewriting theory perspective. We construct finite convergent presentations for these monoids in a general way using Littelmann paths. Moreover, we study the latter presentations in terms of Kashiwara’s crystal graphs for type C. By introducing the admissible column generators, we obtain a finite convergent presentation of the plactic monoid of type C with explicit relations. This approach should allow us to study the syzygy problem for the presentations of plactic monoids for any type
45
Pasku, Elton. "Finiteness conditions for monoids and small categories." Thesis, University of Glasgow, 2006. http://theses.gla.ac.uk/6171/.
Full textAbstract:
Chapter 1 covers some basic notions and results from Algebraic Topology such as CW-complexes, homotopy and homology groups of a space in general and cellular homology for CW-complexes in particular. Also we give some basic ideas from abstract reduction systems and some supporting material such as several order relations on a set and the Knuth-Bendix completion procedure. There are only two original results of the author in this chapter, Theorem 1.4.5 and Theorem 1.7.3. The material related to Topology and Homological Algebra can be found in [12], [21], [40], [62], [82], [91] and [92]. The material related to reduction systems can be found in [5] and [11]. The original work of the author is included in Chapters 2, 3 and 4 apart from Section 3.2 which contains general notions from Category Theory, Section 3.5.2 which contains an account of the work in [67] and Section 4.1 which contains some basics from Combinatorial Semigroup Theory. The results of Section 4.2 are part of [83] which is accepted for publication in the International Journal of Algebra and Computation. The material related to Category Theory can be found in [59], [64], [66], [67], [74], [75], [76], [82] and [93]. The material related to Semigroup Theory is in [24] and [34].In Chapter 2 we show that for every monoid S which is given by a finite and complete presentation P = P[x, r], and for every n ~ 2, there is a chain of CW-complexes such that ~n has dimension n, for every 2 ~ s ~ n the s-skeleton of ~n is ~s and F acts on ~n. This action is called translation. Also we show that, for 2 ~ s ~ n, the open s-cells of ~n are in a 1-1 correspondence with the s-tuples of positive edges of V with the same initial. For the critical s-tuples, the corresponding open s-cells are denoted by Ps-I and the set of their open translates by F.Ps-I.F. The following holds true. if s ~ 3 if s = 2, where U stands for the disjoint union. Also, for every 2 ~ s ~ n - 1, there exists a cellular equivalence "'s on Ks = (~s X ~8)(s+1) such that Ks/ "'s= (V, PI, ... ,Ps-I) and the following is an exact sequence of (ZS, ZS)-bimodules where (D, Pl, ... , Ps-2) = V if s = 2. Using the above short exact sequences, we deduce that S is of type bi-FPn and that the free fi~ite resolution of'lS is S-graded. In Chapter 3 we generalize the notions left-(respectively right)-FPn and bi-FPn for small categories and show that bi-FPn implies left-(respectively right)-FPn . Also we show that another condition, which was introduced by Malbos and called FPn , implies bi-FPn . Since the name FPn is confusing, we call it here f-FPn for a reason which will be made clear in Section 3.1. Restricting to monoids, we show that, if a monoid is given by a finite and complete presentation, then it is of type f-FPn . Lastly, for every small category C, we show how to construct free resolutions of ZC, at lea..'lt up to dimension 3, using some geometrical ideas which can be generalized to construct free resolutions of ZC of any length. vi In Chapter 4 we study finiteness conditions of ~onoids of a combinatorial nature. We show that there are semigroups S in which min'R., is independent of other conditions which S may satisfy such as being finitely generated, periodic, inverse, E-unitary and even from the finiteness of the maximal subgroups of S. We also relate the congruences of a monoid with the finiteness condition minQ, and show that, if S is a monoid which satisfies minQ, then every congruence JC on S which contains Q is of finite index in S. If a semigroup satisfies minQ and has all its maximal subgroups locally finite, then we show that it is finite. Lastly, we show that, for trees of completely O-simple semigroups, the local finiteness of its maximal subgroups implies the local finiteness of the semigroups.
46
Rozoy, Brigitte. "Un modele de parallelisme : le monoide distribue." Caen, 1987. http://www.theses.fr/1987CAEN2039.
Full textAbstract:
La mise en evidence d'equivalences des modeles mathematiques du parallelisme asynchrone nous amene a creer un nouveau modele dit monoide distribue qui constitue les differents modeles existants. Les problemes de cette etude sont la reconnaissabilite dans ce monoide et la terminaison distribuee dans les reseaux repartis asynchrones
47
Grosshans, Nathan. "The limits of Nečiporuk's method and the power of programs over monoids taken from small varieties of finite monoids." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLN028/document.
Full textAbstract:
Cette thèse porte sur des minorants pour des mesures de complexité liées à des sous-classes de la classe P de langages pouvant être décidés en temps polynomial par des machines de Turing. Nous considérons des modèles de calcul non uniformes tels que les programmes sur monoïdes et les programmes de branchement. Notre première contribution est un traitement abstrait de la méthode de Nečiporuk pour prouver des minorants, indépendamment de toute mesure de complexité spécifique. Cette méthode donne toujours les meilleurs minorants connus pour des mesures telles que la taille des programmes de branchements déterministes et non déterministes ou des formules avec des opérateurs booléens binaires arbitraires ; nous donnons une formulation abstraite de la méthode et utilisons ce cadre pour démontrer des limites au meilleur minorant obtenable en utilisant cette méthode pour plusieurs mesures de complexité. Par là, nous confirmons, dans ce cadre légèrement plus général, des résultats de limitation précédemment connus et exhibons de nouveaux résultats de limitation pour des mesures de complexité auxquelles la méthode de Nečiporuk n'avait jamais été appliquée. Notre seconde contribution est une meilleure compréhension de la puissance calculatoire des programmes sur monoïdes issus de petites variétés de monoïdes finis. Les programmes sur monoïdes furent introduits à la fin des années 1980 par Barrington et Thérien pour généraliser la reconnaissance par morphismes et ainsi obtenir une caractérisation en termes de semi-groupes finis de NC^1 et de ses sous-classes. Étant donné une variété V de monoïdes finis, on considère la classe P(V) de langages reconnus par une suite de programmes de longueur polynomiale sur un monoïde de V : lorsque l'on fait varier V parmi toutes les variétés de monoïdes finis, on obtient différentes sous-classes de NC^1, par exemple AC^0, ACC^0 et NC^1 quand V est respectivement la variété de tous les monoïdes apériodiques finis, résolubles finis et finis. Nous introduisons une nouvelle notion de docilité pour les variétés de monoïdes finis, renforçant une notion de Péladeau. L'intérêt principal de cette notion est que quand une variété V de monoïdes finis est docile, nous avons que P(V) contient seulement des langages réguliers qui sont quasi reconnus par morphisme par des monoïdes de V. De nombreuses questions ouvertes à propos de la structure interne de NC^1 seraient réglées en montrant qu'une variété de monoïdes finis appropriée est docile, et, dans cette thèse, nous débutons modestement une étude exhaustive de quelles variétés de monoïdes finis sont dociles. Plus précisément, nous portons notre attention sur deux petites variétés de monoïdes apériodiques finis bien connues : DA et J. D'une part, nous montrons que DA est docile en utilisant des arguments de théorie des semi-groupes finis. Cela nous permet de dériver une caractérisation algébrique exacte de la classe des langages réguliers dans P(DA). D'autre part, nous montrons que J n'est pas docile. Pour faire cela, nous présentons une astuce par laquelle des programmes sur monoïdes de J peuvent reconnaître beaucoup plus de langages réguliers que seulement ceux qui sont quasi reconnus par morphisme par des monoïdes de J. Cela nous amène à conjecturer une caractérisation algébrique exacte de la classe de langages réguliers dans P(J), et nous exposons quelques résultats partiels appuyant cette conjecture. Pour chacune des variétés DA et J, nous exhibons également une hiérarchie basée sur la longueur des programmes à l'intérieur de la classe des langages reconnus par programmes sur monoïdes de la variété, améliorant par là les résultats de Tesson et Thérien sur la propriété de longueur polynomiale pour les monoïdes de ces variétés<br>This thesis deals with lower bounds for complexity measures related to subclasses of the class P of languages that can be decided by Turing machines in polynomial time. We consider non-uniform computational models like programs over monoids and branching programs.Our first contribution is an abstract, measure-independent treatment of Nečiporuk's method for proving lower bounds. This method still gives the best lower bounds known on measures such as the size of deterministic and non-deterministic branching programs or formulae{} with arbitrary binary Boolean operators; we give an abstract formulation of the method and use this framework to prove limits on the best lower bounds obtainable using this method for several complexity measures. We thereby confirm previously known limitation results in this slightly more general framework and showcase new limitation results for complexity measures to which Nečiporuk's method had never been applied.Our second contribution is a better understanding of the computational power of programs over monoids taken from small varieties of finite monoids. Programs over monoids were introduced in the late 1980s by Barrington and Thérien as a way to generalise recognition by morphisms so as to obtain a finite-semigroup-theoretic characterisation of NC^1 and its subclasses. Given a variety V of finite monoids, one considers the class P(V) of languages recognised by a sequence of polynomial-length programs over a monoid from V: as V ranges over all varieties of finite monoids, one obtains different subclasses of NC^1, for instance AC^0, ACC^0 and NC^1 when V respectively is the variety of all finite aperiodic, finite solvable and finite monoids. We introduce a new notion of tameness for varieties of finite monoids, strengthening a notion of Péladeau. The main interest of this notion is that when a variety V of finite monoids is tame, we have that P(V) does only contain regular languages that are quasi morphism-recognised by monoids from V. Many open questions about the internal structure of NC^1 would be settled by showing that some appropriate variety of finite monoids is tame, and, in this thesis, we modestly start an exhaustive study of which varieties of finite monoids are tame. More precisely, we focus on two well-known small varieties of finite aperiodic monoids: DA and J. On the one hand, we show that DA is tame using finite-semigroup-theoretic arguments. This allows us to derive an exact algebraic characterisation of the class of regular languages in P(DA). On the other hand, we show that J is not tame. To do this, we present a trick by which programs over monoids from J can recognise much more regular languages than only those that are quasi morphism-recognised by monoids from J. This brings us to conjecture an exact algebraic characterisation of the class of regular languages in P(J), and we lay out some partial results that support this conjecture. For each of the varieties DA and J, we also exhibit a program-length-based hierarchy within the class of languages recognised by programs over monoids from the variety, refining Tesson and Thérien's results on the polynomial-length property for monoids from those varieties
48
Pirashvili, Ilia. "The fundamental groupoid and the geometry of monoids." Thesis, University of Leicester, 2016. http://hdl.handle.net/2381/37837.
Full textAbstract:
This thesis is divided in two equal parts. We start the first part by studying the Kato-spectrum of a commutative monoid M, denoted by KSpec(M). We show that the functor M → KSpec(M) is representable and discuss a few consequences of this fact. In particular, when M is additionally finitely generated, we give an efficient way of calculating it explicitly. We then move on to study the cohomology theory of monoid schemes in general and apply it to vector- and particularly, line bundles. The isomorphism class of the latter is the Picard group. We show that under some assumptions on our monoid scheme X, if k is an integral domain (resp. PID), then the induced map Pic(X) → Pic(Xk) from X to its realisation is a monomorphism (resp. isomorphism). We then focus on the Pic functor and show that it respects finite products. Finally, we generalise several important constructions and notions such as cancellative monoids, smoothness and Cartier divisors, and prove important results for them. The main results of the second part can be summed up in fewer words. We prove that for good topological spaces X the assignment U → II₁(U) is the terminal object of the 2-category of costacks. Here U is an open subset of X and II₁(U) denotes the fundamental groupoid of U. This result translates to the étale fundamental groupoid as well, though the proof there is completely different and involves studying and generalising Galois categories.
49
Simmons, Christopher Paul. "Small category theory applied to semigroups and monoids." Thesis, University of York, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.249334.
Full text
50
Tunsi, Laila. "Ample monoids and the theory of small categories." Thesis, University of York, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.423599.
Full text