Narrow Results

The syntactic complexity of a subclass of the class of regular languages is the maximal cardinality of syntactic semigroups of languages in that class, taken as a function of the state complexity n of these languages. We prove that n! and ⌊e(n − 1)⌋. are tight upper bounds for the syntactic complexity of ℛ- and 𝒥-trivial regular languages, respectively.

We show that the left regular representation π_l of a discrete quantum group (A, Δ) has the absorbing property and forms a monoid in the representation category Rep(A, Δ).

Next we show that an absorbing monoid in an abstract tensor *-category gives rise to an embedding functor (or fiber functor) , and we identify conditions on the monoid, satisfied by , implying that E is *-preserving.

As is well-known, from an embedding functor the generalized Tannaka theorem produces a discrete quantum group (A, Δ) such that . Thus, for a C*-tensor category with conjugates and irreducible unit the following are equivalent: (1) is equivalent to the representation category of a discrete quantum group (A, Δ), (2) admits an absorbing monoid, (3) there exists a *-preserving embedding functor .

We continue the study of OP_n, the monoids of orientation-preserving mappings on a chain, leading to the study of the semigroup pseudovariety generated by all monoids OP_n, showing among other results that is self-dual and contains all commutative semigroups.

We consider universal algebras which are monoids and which have a binary operation we call internalized equality, satisfying some natural conditions. We show that the class of such E-structures has a characterization in terms of a distinguished submonoid which is a semilattice. Some important varieties (and variety-like classes) of E-structures are considered, including E-semilattices (which we represent in terms of topological spaces), E-rings (which we show are equivalent to rings with a generalized interior operation), E-quantales (where internalized equalities on a fixed quantale in which 1 is the largest element are shown to correspond to sublocales of the quantale), and EI-structures (in which an internalized inequality is defined and interacts in a natural way with the equality operation).

Monoids that can be presented by a finite complete rewriting system have both finite derivation type and finite homological type. This paper introduces a higher dimensional analogue of each of these invariants, and relates them to homological finiteness conditions.

Given a complete rewriting system R on X and a subset X₀ of X⁺ satisfying certain conditions, we present a complete rewriting system for the submonoid of M(X;R) generated by X₀. The obtained result will be applied to the group of units of a monoid satisfying H₁ = D₁. On the other hand we prove that all maximal subgroups of a monoid defined by a special rewriting system are isomorphic.

In this paper we prove that the pseudovariety of Abelian groups is hyperdecidable and moreover that it is completely tame. This is a consequence of the fact that a system of group equations on a free Abelian group with certain rational constraints is solvable if and only if it is solvable in every finite quotient.

A finite poset (P ≼ S) determines a finite dimensional algebra T_P over the field 𝔽 of two elements, with an upper triangular representation. We determine the structure of the radical of the representation algebra A of the monoid (T_P,·) over a field of characteristic different from 2. We also consider degenerations of A over a complete discrete valuation ring with residue field of characteristic 2.

We continue our program of extending key techniques from geometric group theory to semigroup theory, by studying monoids acting by isometric embeddings on spaces equipped with asymmetric, partially defined distance functions. The canonical example of such an action is a cancellative monoid acting by translation on its Cayley graph. Our main result is an extension of the Švarc–Milnor lemma to this setting.

A monoid M is called surjunctive if every injective cellular automata with finite alphabet over M is surjective. We show that all finite monoids, all finitely generated commutative monoids, all cancellative commutative monoids, all residually finite monoids, all finitely generated linear monoids, and all cancellative one-sided amenable monoids are surjunctive. We also prove that every limit of marked surjunctive monoids is itself surjunctive. On the other hand, we show that the bicyclic monoid and, more generally, all monoids containing a submonoid isomorphic to the bicyclic monoid are non-surjunctive.

The class of finitely presented algebras over a field $K$ with a set of generators $a_1,\dots ,a_n$ and defined by homogeneous relations of the form $a_1{a}_2\cdots a_n=a_{\sigma (1)}{a}_{\sigma (2)}\cdots a_{\sigma (n)}$, where $\sigma$ runs through a subset $H$ of the symmetric group ${Sym}_n$ of degree $n$, is investigated. Groups $H$ in which the cyclic group $〈(1,2,\dots ,n)〉$ is a normal subgroup of index $2$ are considered. Certain representations by permutations of the dihedral and semidihedral groups belong to this class of groups. A normal form for the elements of the underlying monoid $S_n(H)$ with the same presentation as the algebra is obtained. Properties of the algebra are derived, it follows that it is an automaton algebra in the sense of Ufnarovskij. The universal group $G_n$ of $S_n(H)$ is a unique product group, and it is the central localization of a cancellative subsemigroup of $S_n(H)$. This, together with previously obtained results on such semigroups and algebras, is used to show that the algebra $K[S_n(H)]$ is semiprimitive.

Leech’s (co)homology groups of finite cyclic monoids are computed.

We define the product of admissible abstract kernels of the form $\mathrm{\Phi }:M\to \frac{\mathrm{\text{End}}(G)}{\mathrm{\text{Inn}}(G)}$, where $M$ is a monoid, $G$ is a group and $\mathrm{\Phi }$ is a monoid homomorphism. Identifying $C$-equivalent abstract kernels, where $C$ is the center of $G$, we obtain that the set ${ℳ}(M,C)$ of $C$-equivalence classes of admissible abstract kernels inducing the same action of $M$ on $C$ is a commutative monoid. Considering the submonoid ${ℒ}(M,C)$ of abstract kernels that are induced by special Schreier extensions, we prove that the factor monoid ${𝒜}(M,C)=\frac{{ℳ}(M,C)}{{ℒ}(M,C)}$ is an abelian group. Moreover, we show that this abelian group is isomorphic to the third cohomology group $H^3(M,C)$.

It is known, since the early 2000s, that the Catalan monoid $C_n$ generated by $n$ elements is finitely based if and only if $n\le 3$. The main goal of this paper is to prove that the involution monoid $(C_3,{}^{*})$ is non-finitely based. Therefore, in contrast, combining with previous results yields that the involution Catalan monoid $(C_n,{}^{*})$ is finitely based if and only if $n=1$.

The Kiselman monoid $K_n$ generated by $n$ elements is also considered. Although the semigroups $C_n$ and $K_n$ have recently been shown to satisfy the same identities, it is unknown if the same result holds when they are considered as involution semigroups. Nevertheless, it is deduced from the main result that the involution Kiselman monoid $(K_n,{}^{*})$ is finitely based if and only if $n=1$.

This paper determines relations between two notions concerning monoids: factorability structure, introduced to simplify the bar complex; and quadratic normalization, introduced to generalize quadratic rewriting systems and normalizations arising from Garside families. Factorable monoids are characterized in the axiomatic setting of quadratic normalizations. Additionally, quadratic normalizations of class $\left(4,3\right)$ are characterized in terms of factorability structures and a condition ensuring the termination of the associated rewriting system.

A variety of algebras is called Cross if it is finitely based, finitely generated, and has finitely many subvarieties. In this paper, we classify all Cross varieties of aperiodic monoids with commuting idempotents.

In this paper, we study the complexity of deciding code and monoid properties for regular sets specified by deterministic or nondeterministic finite automata. The results are as follows. The code problem for regular sets specified by deterministic or nondeterministic finite automata is NL-complete under NC⁽¹⁾ reducibilities. The problems of determining whether a regular set given by a deterministic finite automaton is a monoid or a free monoid or a finitely generated monoid are all NL-complete under NC⁽¹⁾ reducibilities. These monoid problems become PSPACE-complete if the regular sets are specified by nondeterministic finite automata instead. The maximal code problem for deterministic finite automata is shown to be in DET and NL-hard, while a PSPACE upper bound and NP-hardness lower bound hold for the case of nondeterministic finite automata.

Using purely syntactical arguments, it is shown that every nontrivial pseudovariety of monoids contained in DO whose corresponding variety of languages is closed under unambiguous product, for instance DA, is local in the sense of Tilson.

We prove that the singular braid monoid of [2] and [5] embeds in a group. This group has a geometric interpretation as singular braids with two type of singularities which cancel.

We study finitary $2$-categories associated to dual projection functors for finite-dimensional associative algebras. In the case of path algebras of admissible tree quivers (which includes all Dynkin quivers of type $A$), we show that the monoid generated by dual projection functors is the Hecke–Kiselman monoid of the underlying quiver and also obtain a presentation for the monoid of indecomposable subbimodules of the identity bimodule.