Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTwo variants of the Froiduire-Pin Algorithm for finite semigroups
260
0
0.0
(
0
)
Added by
James Mitchell
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper, we present two algorithms based on the Froidure-Pin Algorithm for computing the structure of a finite semigroup from a generating set. As was the case with the original algorithm of Froidure and Pin, the algorithms presented here produce the left and right Cayley graphs, a confluent terminating rewriting system, and a reduced word of the rewriting system for every element of the semigroup. If $U$ is any semigroup, and $A$ is a subset of $U$, then we denote by $langle Arangle$ the least subsemigroup of $U$ containing $A$. If $B$ is any other subset of $U$, then, roughly speaking, the first algorithm we present describes how to use any information about $langle Arangle$, that has been found using the Froidure-Pin Algorithm, to compute the semigroup $langle Acup Brangle$. More precisely, we describe the data structure for a finite semigroup $S$ given by Froidure and Pin, and how to obtain such a data structure for $langle Acup Brangle$ from that for $langle Arangle$. The second algorithm is a lock-free concurrent version of the Froidure-Pin Algorithm.
rate research
Read More
A family $mathcal L$ of subsets of a set $X$ is called linked if $Acap B eemptyset$ for any $A,Binmathcal L$. A linked family $mathcal M$ of subsets of $X$ is maximal linked if $mathcal M$ coincides with each linked family $mathcal L$ on $X$ that contains $mathcal M$. The superextension $lambda(X)$ of $X$ consists of all maximal linked families on $X$. Any associative binary operation $* : Xtimes X to X$ can be extended to an associative binary operation $*: lambda(X)timeslambda(X)tolambda(X)$. In the paper we study automorphisms of the superextensions of finite monogenic semigroups and characteristic ideals in such semigroups. In particular, we describe the automorphism groups of the superextensions of finite monogenic semigroups of cardinality $leq 5$.
This note proves a generalisation to inverse semigroups of Anisimovs theorem that a group has regular word problem if and only if it is finite, answering a question of Stuart Margolis. The notion of word problem used is the two-tape word problem -- the set of all pairs of words over a generating set for the semigroup which both represent the same element.
As an appropriate generalisation of the features of the classical (Schein) theory of representations of inverse semigroups in $mathscr{I}_{X}$, a theory of representations of inverse semigroups by homomorphisms into complete atomistic inverse algebras is developed. This class of inverse algebras includes partial automorphism monoids of entities such as graphs, vector spaces and modules. A workable theory of decompositions is reached; however complete distributivity is required for results approaching those of the classical case.
Brauer and Fowler noted restrictions on the structure of a finite group G in terms of the order of the centralizer of an involution t in G. We consider variants of these themes. We first note that for an arbitrary finite group G of even order, we have |G| is less than the number of conjugacy classes of the Fitting subgroup times the order of the centralizer to the fourth power of any involution in G. This result does require the classification of the finite simple groups. The groups SL(2,q) with q even shows that the exponent 4 cannot be replaced by any exponent less than 3. We do not know at present whether the exponent 4 can be improved in general, though we note that the exponent 3 suffices for almost simple groups G. We are however able to prove that every finite group $G$ of even order contains an involution u such that [G:F(G)] is less than the cube of the order of the centralizer of u. There is a dichotomy in the proof of this fact, as it reduces to proving two residual cases: one in which G is almost simple (where the classification of the finite simple groups is needed) and one when G has a Sylow 2-subgroup of order 2. For the latter result, the classification of finite simple groups is not needed (though the Feit-Thompson odd order theorem is). We also prove a very general result on fixed point spaces of involutions in finite irreducible linear groups which does not make use of the classification of the finite simple groups, and some other results on the existence of non-central elements (not necessarily involutions) with large centralizers in general finite groups. We also show (without the classification of finite simple groups) that if t is an involution in G and p is a prime divisor of [G:F(G)], then p is at most 1 plus the order of the centralizer of t (and this is best possible).
We present a survey of results on profinite semigroups and their link with symbolic dynamics. We develop a series of results, mostly due to Almeida and Costa and we also include some original results on the Schutzenberger groups associated to a uniformly recurrent set.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
