Narrow Results

Wilf Conjecture on numerical semigroups is a question posed by Wilf in 1978 and is an inequality connecting the Frobenius number, embedding dimension and the genus of the semigroup. The conjecture is still open in general. We prove that this Wilf inequality is preserved under gluing of numerical semigroups. If the numerical semigroups minimally generated by $A=\{a_1,\dots ,a_p\}$ and $B=\{b_1,\dots ,b_q\}$ satisfy the Wilf inequality, then so does their gluing which is minimally generated by $C=k_{1}A\bigsqcup k_{2}B$. We discuss the extended Wilf’s Conjecture in higher dimensions for certain affine semigroups and prove an analogous result.

Free dcpo semigroups play an important role in modeling the semantics of nondeterministic programming languages. In this paper, we provide concrete constructions for free dcpo semigroups, free domain bands (with additional inequalities), and free dcpo groups. They are the noncommutative generalizations of the classical Plotkin (Smyth, Hoare) powerdomains.

In a preceding paper (Bruyère and Carton, automata on linear orderings, MFCS'01), automata have been introduced for words indexed by linear orderings. These automata are a generalization of automata for finite, infinite, bi-infinite and even transfinite words studied by Büchi. Kleene's theorem has been generalized to these words. We prove that rational sets of words on countable scattered linear orderings are closed under complementation using an algebraic approach.

Let U₀, U₁, …, U_n be a (finite or infinite) sequence of semigroups of isometries which act on the same separable Hilbert space H, n = 1, 2, …, ∞. {U_j} is said to be orthogonal if for all i ≠ j we have

The purpose of this paper is to study semigroups of *-endomorphisms of type I factors, with parameters in a countable dense subgroup of the real line. Most of our results are motivated by the theory of semigroups of isometries. It is shown that every semigroup of *-endomorphisms can be extended to a group of *-automorphisms in a minimal way. In certain situations, it is shown that a semigroup of *-endomorphisms can be decomposed into three simpler semigroups. Shifts are defined and classified up to outer conjugacy.

We consider the relationship between the combinatorial properties of semigroupoids in general and semigroups in particular. We show that a semigroupoid is finitely generated [finitely presentable] exactly if the corresponding categorical-at-zero semigroup is finitely generated [respectively, finitely presentable]. This allows us to extend some of the main results of [17], to show that finite generation and presentability are preserved under finite extension of semigroupoids and the taking of cofinite subsemigroupoids. We apply this result to extend the results of [6], giving characterizations of finite generation and finite presentability in Rees matrix semigroups over semigroupoids.

We show that a number of natural membership problems for classes associated with finite semigroups are computationally difficult. In particular, we construct a 55-element semigroup S such that the finite membership problem for the variety of semigroups generated by S interprets the graph 3-colorability problem.

A semigroup is complex if it generates a variety with the property that every finite lattice is embeddable in its subvariety lattice. In this paper, subvariety lattices of varieties generated by small semigroups will be investigated. Specifically, all complex semigroups of minimal order will be identified.

Recently it has been noticed that many interesting combinatorial objects belong to a class of semigroups called left regular bands, and that random walks on these semigroups encode several well-known random walks. For example, the set of faces of a hyperplane arrangement is endowed with a left regular band structure. This paper studies the module structure of the semigroup algebra of an arbitrary left regular band, extending results for the semigroup algebra of the faces of a hyperplane arrangement. In particular, a description of the quiver of the semigroup algebra is given and the Cartan invariants are computed. These are used to compute the quiver of the face semigroup algebra of a hyperplane arrangement and to show that the semigroup algebra of the free left regular band is isomorphic to the path algebra of its quiver.

A variety is said to be a Rees–Sushkevich variety if it is contained in a periodic variety generated by 0-simple semigroups. It is shown that all combinatorial Rees–Sushkevich varieties are finitely based.

A gap in the proof of Proposition 4.5 in the article cited in the heading is mended.

Let S be a finite semigroup. In this paper, we introduce the functions φ_s:S* → S*, first defined by Rhodes, given by φ_s([a₁,a₂,…,a_n]) = [sa₁,sa₁a₂,…,sa₁a₂ ⋯ a_n]. We show that if S is a finite aperiodic semigroup, then the semigroup generated by the functions {φ_s}_{s ∈ S} is finite and aperiodic.

I discuss Bret Tilson's life, both personal and mathematical, and his impact on semigroup theory.

This is an introduction to Bret Tilson's paper "Modules".

Let T_n be the full transformation semigroup of a finite set, say X_n = {1, 2, …, n}, and for a given full transformation α : X_n → X_n let F(α) = {x ∈ X_n : xα = x} be its set of fixed points. In this note we obtain and discuss formulae for F(n, r, k) = |{α ∈ T_n : |Im α| = r ∧ |F(α)| = k}|.

Automatic presentations, also called FA-presentations, were introduced to extend finite model theory to infinite structures whilst retaining the solubility of interesting decision problems. A particular focus of research has been the classification of those structures of some species that admit automatic presentations. Whilst some successes have been obtained, this appears to be a difficult problem in general. A restricted problem, also of significant interest, is to ask this question for unary automatic presentations: automatic presentations over a one-letter alphabet. This paper studies unary FA-presentable semigroups. We prove the following: Every unary FA-presentable structure admits an injective unary automatic presentation where the language of representatives consists of every word over a one-letter alphabet. Unary FA-presentable semigroups are locally finite, but non-finitely generated unary FA-presentable semigroups may be infinite. Every unary FA-presentable semigroup satisfies some Burnside identity. We describe the Green's relations in unary FA-presentable semigroups. We investigate the relationship between the class of unary FA-presentable semigroups and various semigroup constructions. A classification is given of the unary FA-presentable completely simple semigroups.

It is shown that if 𝖵 is a local monoidal pseudovariety of semigroups, then 𝖪 ⓜ 𝖵, 𝖣 ⓜ 𝖵 and are local. Other operators of the form 𝖹 ⓜ(_) are considered. In the process, results about the interplay between operators 𝖹 ⓜ(_) and (_) _* 𝖣_k are obtained.

A group is Markov if it admits a prefix-closed regular language of unique representatives with respect to some generating set, and strongly Markov if it admits such a language of unique minimal-length representatives over every generating set. This paper considers the natural generalizations of these concepts to semigroups and monoids. Two distinct potential generalizations to monoids are shown to be equivalent. Various interesting examples are presented, including an example of a non-Markov monoid that nevertheless admits a regular language of unique representatives over any generating set. It is shown that all finitely generated commutative semigroups are strongly Markov, but that finitely generated subsemigroups of virtually abelian or polycyclic groups need not be. Potential connections with word-hyperbolic semigroups are investigated. A study is made of the interaction of the classes of Markov and strongly Markov semigroups with direct products, free products, and finite-index subsemigroups and extensions. Several questions are posed.

We study the complexity classes 𝖯 and 𝖭𝖯 through a semigroup 𝖿𝖯 ("polynomial-time functions"), consisting of all polynomially balanced polynomial-time computable partial functions. The semigroup 𝖿𝖯 is non-regular if and only if 𝖯 ≠ 𝖭𝖯. The one-way functions considered here are based on worst-case complexity (they are not cryptographic); they are exactly the non-regular elements of 𝖿𝖯. We prove various properties of 𝖿𝖯, e.g. that it is finitely generated. We define reductions with respect to which certain universal one-way functions are 𝖿𝖯-complete.

This paper continues the functional approach to the $\mathrm{\text{P}}$-vs.-$\mathrm{\text{NP}}$ problem, begun in [J. C. Birget, Semigroups and one-way functions, Internat. J. Algebra Comput.25 (1–2) (2015) 3–36]. Here, we focus on the monoid ${{ℛ}{ℳ}}_2^P$ of right-ideal morphisms of the free monoid, that have polynomial input balance and polynomial time-complexity. We construct a machine model for the functions in ${{ℛ}{ℳ}}_2^P$, and evaluation functions. We prove that, ${{ℛ}{ℳ}}_2^P$ is not finitely generated, and use this to show separation results for time-complexity.