On the complexity of the word problem for automaton semigroups and automaton groups

In this paper, we study the word problem for automaton semigroups and automaton groups from a complexity point of view. As an intermediate concept between automaton semigroups and automaton groups, we introduce automaton-inverse semigroups, which are generated by partial, yet invertible automata. We show that there is an automaton-inverse semigroup and, thus, an automaton semigroup with a PSpace-complete word problem. We also show that there is an automaton group for which the word problem with a single rational constraint is PSpace-complete. Additionally, we provide simpler constructions for the uniform word problems of these classes. For the uniform word problem for automaton groups (without rational constraints), we show NL-hardness. Finally, we investigate a question asked by Cain about a better upper bound for the length of a word on which two distinct elements of an automaton semigroup must act differently.A detailed listing of the contributions of this paper can be found at the end of this paper.     

The oversemigroups of a numerical semigroup

We study the set of numerical semigroups containing a given numerical semigroup. As an application we prove characterizations of irreducible numerical semigroups that unify some of the existing characterizations for symmetric and pseudo-symmetric numerical semigroups. Finally we describe an algorithm for computing a minimal decomposition of a numerical semigroup in terms of irreducible numerical semigroups.     

The Oversemigroups of a Numerical Semigroup

Abstract. We study the set of numerical semigroups containing a given numerical semigroup. As an application we prove characterizations of irreducible numerical semigroups that unify some of the existing characterizations for symmetric and pseudo-symmetric numerical semigroups. Finally we describe an algorithm for computing a minimal decomposition of a numerical semigroup in terms of irreducible numerical semigroups.     

Irreducible numerical semigroups with multiplicity three and four

In this paper we analyze the irreducibility of numerical semigroups with multiplicity up to four. Our approach uses the notion of Kunz-coordinates vector of a numerical semigroup recently introduced in Blanco and Puerto (SIAM J. Discrete Math., 26(3):1210–1237, 2012). With this tool we also completely describe the whole family of minimal decompositions into irreducible numerical semigroups with the same multiplicity for this set of numerical semigroups. We give detailed examples to show the applicability of the methodology and conditions for the irreducibility of well-known families of numerical semigroups such as those that are generated by a generalized arithmetic progression.     

The arithmetic extensions of a numerical semigroup

Abstract

In this paper we introduce the notion of extension of a numerical semigroup. We provide a characterization of the numerical semigroups whose extensions are all arithmetic and we give an algorithm for the computation of the whole set of arithmetic extension of a given numerical semigroup. As by-product, new explicit formulas for the Frobenius number and the genus of proportionally modular semigroups are obtained.     

The ordinarization transform of a numerical semigroup and semigroups with a large number of intervals

A numerical semigroup is said to be ordinary if it has all its gaps in a row. Indeed, it contains zero and all integers from a given positive one. One can define a simple operation on a non-ordinary semigroup, which we call here the ordinarization transform, by removing its smallest non-zero non-gap (the multiplicity) and adding its largest gap (the Frobenius number). This gives another numerical semigroup and by repeating this transform several times we end up with an ordinary semigroup. The genus, that is, the number of gaps, is kept constant in all the transforms.This procedure allows the construction of a tree for each given genus containing all semigroups of that genus and rooted in the unique ordinary semigroup of that genus. We study here the regularity of these trees and the number of semigroups at each depth. For some depths it is proved that the number of semigroups increases with the genus and it is conjectured that this happens at all given depths. This may give some light to a former conjecture saying that the number of semigroups of a given genus increases with the genus.We finally give an identification between semigroups at a given depth in the ordinarization tree and semigroups with a given (large) number of gap intervals and we give an explicit characterization of those semigroups.     

Proportionally Modular Diophantine Inequalities and Full Semigroups

A proportionally modular numerical semigroup is the set of nonnegative integer solutions to a Diophantine inequality of the type ax mod b ≤ cx. We give a new presentation for these semigroups and we relate them with a type of affine full semigroups. Next, we describe explicitly the minimal generating system for the affine full semigroups we are considering. As a consequence, we obtain generating systems for proportionally modular numerical semigroups and we exhibit several families of these semigroups in terms of their generators. Finally, we use the concept of fundamental gap to study when a proportionally modular numerical semigroup is symmetric and we propose some open problems.     

Clifford半群的E-扩张

半群扩张是以已知的或者较简单的半群类为基础,借助某种方法扩张成一类半群.本文讨论Cliffbrd半群借助Mum半群TE的扩张.引入了这种扩张的概念并给出一个具体的例子.还给出Clifford半群有E扩张的必要条件.证明了满逆半群的Green关系等价类在Munn表示下的同态象仍是同样的等价类.     

Filters in (Quasiordered) Semigroups and Lattices of Filters

A filter in a semigroup is a subsemigroup whose complement is an ideal. (Alternatively, in a quasiordered semigroup, a slightly more general definition can be given.) We prove a number of results related to filters in a semigroup and the lattice of filters of a semigroup. For instance, we prove that every complete algebraic lattice can be the lattice of filters of a semigroup. We prove that every finite semigroup is a homomorphic image of a finite semigroup whose lattice of filters is boolean and which belongs to the pseudovariety generated by the original semigroup. We describe filter lattices of some well-known semigroups such as full transformation semigroups of finite sets (which are three-element chains) and free semigroups (which are boolean).     

Fundamental Gaps in Numerical Semigroups with Respect to Their Multiplicity

For a numerical semigroup, we introduce the concept of a fundamental gap with respect tothe multiplicity of the semigroup.The semigroup is fully determined by its multiplicity and these gaps.We study the case when a set of non-negative integers is the set of fundamental gaps with respect to themultiplicity of a numerical semigroup.Numerical semigroups with maximum and mininmm number ofthis kind of gaps are described.     

Fundamental Gaps in Numerical Semigroups with Respect to Their Multiplicity

For a numerical semigroup, we introduce the concept of a fundamental gap with respect to the multiplicity of the semigroup. The semigroup is fully determined by its multiplicity and these gaps.We study the case when a set of non-negative integers is the set of fundamental gaps with respect to the multiplicity of a numerical semigroup, Numerical semigroups with maximum and minimum number of this kind of gaps are described.     

Gorenstein Curves with Quasi-Symmetric Weierstrass Semigroups

We consider a canonical Gorenstein curve C of arithmetic genus g in P g-1 (K), that admits a non-singular point P, whose Weierstrass semigroup is quasi-symmetric in the sense that the last gap is equal to 2g-2. By making local considerations at the point P and the second point of the curve C on its osculating hyperplane at P we construct monomial bases for the spaces of higher order regular differentials. We give an irreducibility criterion for the canonical curve in terms of the coefficients of the quadratic relations. We also realize each quasi-symmetric numerical semigroup as the Weierstrass semigroup of a reducible canonical Gorenstein curve, but we give examples of such semigroups that cannot be realized as Weierstrass semigroups of smooth curves.     

A Pettis-type integral and applications to transition semigroups

Motivated by applications to transition semigroups, we introduce the notion of a norming dual pair and study a Pettis-type integral on such pairs. In particular, we establish a sufficient condition for integrability. We also introduce and study a class of semigroups on such dual pairs which are an abstract version of transition semigroups. Using our results, we give conditions ensuring that a semigroup consisting of kernel operators has a Laplace transform which also consists of kernel operators. We also provide conditions under which a semigroup is uniquely determined by its Laplace transform.     

Varieties and Nilpotent Extensions of Permutative Periodic Semigroups

We investigate certain semigroup varieties formed by nilpotent extensions of orthodox normal bands of commutative periodic groups. Such semigroups are shown to be both structurally periodic and structurally commutative, and are therefore structurally inverse semigroups. Such semigroups are also shown to be dense semilattices of structurally group semigroups. Making use of these structure decompositions, we prove that the subvariety lattice of any variety comprised of such semigroups is isomorphic to the direct product of the following three sublattices: its sublattice of all structurally trivial semigroup varieties, its sublattice of all semilattice varieties, and its sublattice of all group varieties. We conclude, therefore, that to completely describe this lattice, we must first describe completely the lattice of all structurally trivial semigroup varieties, since the other two are well known lattices.     

On the second Feng-Rao distance of Algebraic Geometry codes related to Arf semigroups

We describe the second (generalized) Feng-Rao distance for elements in an Arf numerical semigroup that are greater than or equal to the conductor of the semigroup. This provides a lower bound for the second Hamming weight for one point AG codes. In particular, we can obtain the second Feng-Rao distance for the codes defined by asymptotically good towers of function fields whose Weierstrass semigroups are inductive. In addition, we compute the second Feng-Rao number, and provide some examples and comparisons with previous results on this topic. These calculations rely on Apéry sets, and thus several results concerning Apéry sets of Arf semigroups are presented.     

A generalized Clifford theorem of semigroups

A U-abundant semigroup S in which every H-class of S contains an element in the set of projections U of S is said to be a U-superabundant semigroup.This is an analogue of regular semigroups which are unions of groups and an analogue of abundant semigroups which are superabundant.In 1941,Clifford proved that a semigroup is a union of groups if and only if it is a semilattice of completely simple semigroups.Several years later,Fountain generalized this result to the class of superabundant semigroups.In this p...     

The set of numerical semigroups of a given genus

In this paper we present a new approach to construct the set of numerical semigroups with a fixed genus. Our methodology is based on the construction of the set of numerical semigroups with fixed Frobenius number and genus. An equivalence relation is given over this set and a tree structure is defined for each equivalence class. We also provide a more efficient algorithm based on the translation of a numerical semigroup to its so-called Kunz-coordinates vector.