Log in

Relevant bibliographies by topics / Finite semigroups / Journal articles

To see the other types of publications on this topic, follow the link: Finite semigroups.

Journal articles on the topic 'Finite semigroups'

Author: Grafiati

Published: 7 December 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Finite semigroups.'

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 journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

LE SAEC, BERTRAND, JEAN-ERIC PIN, and PASCAL WEIL. "SEMIGROUPS WITH IDEMPOTENT STABILIZERS AND APPLICATIONS TO AUTOMATA THEORY." International Journal of Algebra and Computation 01, no. 03 (September 1991): 291–314. http://dx.doi.org/10.1142/s0218196791000195.

Full text

Abstract:

Nous prouvons que tout semigroupe fini est quotient d'un semigroupe fini dans lequel les stabilisateurs droits satisfont les identités x = x2 et xy = xyx. Ce resultat a plusieurs consé-quences. Tout d'abord, nous l'utilisons, en même temps qu'un résultat de I. Simon sur les congruences de chemins, pour obtenir une preuve purement algébrique d'un théorème profond de McNaughton sur les mots infinis. Puis, nous donnons une preuve algébrique d'un théorème de Brown sur des conditions de finitude pour les semigroupes. We show that every finite semigroup is a quotient of a finite semigroup in which every right stabilizer satisfies the identities x = x2 and xy = xyx. This result has several consequences. We first use it together with a result of I. Simon on congruences on paths to obtain a purely algebraic proof of a deep theorem of McNaughton on infinite words. Next, we give an algebraic proof of a theorem of Brown on a finiteness condition for semigroups.

APA, Harvard, Vancouver, ISO, and other styles

2

Shoji, Kunitaka. "Regular Semigroups Which Are Amalgamation Bases for Finite Semigroups." Algebra Colloquium 14, no. 02 (June 2007): 245–54. http://dx.doi.org/10.1142/s1005386707000247.

Full text

Abstract:

In this paper, we prove that a completely 0-simple (or completely simple) semigroup is an amalgamation base for finite semigroups if and only if it is an amalgamation base for semigroups. By adopting the same method as used in a previous paper, we prove that a finite regular semigroup is an amalgamation base for finite semigroups if its [Formula: see text]-classes are linearly ordered and all of its principal factor semigroups are amalgamation bases for finite semigroups. Finally, we give an example of a finite semigroup U which is an amalgamation base for semigroups, but not all of its principal factor semigroups are amalgamation bases either for semigroups or for finite semigroups.

APA, Harvard, Vancouver, ISO, and other styles

3

Guo, Xiaojiang, and Lin Chen. "Semigroup algebras of finite ample semigroups." Proceedings of the Royal Society of Edinburgh: Section A Mathematics 142, no. 2 (March 21, 2012): 371–89. http://dx.doi.org/10.1017/s0308210510000715.

Full text

Abstract:

An adequate semigroup S is called ample if ea = a(ea)* and ae = (ae)†a for all a ∈ S and e ∈ E(S). Inverse semigroups are exactly those ample semigroups that are regular. After obtaining some characterizations of finite ample semigroups, it is proved that semigroup algebras of finite ample semigroups have generalized triangular matrix representations. As applications, the structure of the radicals of semigroup algebras of finite ample semigroups is obtained. In particular, it is determined when semigroup algebras of finite ample semigroup are semiprimitive.

APA, Harvard, Vancouver, ISO, and other styles

4

Birget, Jean-Camille, Stuart Margolis, and John Rhodes. "Semigroups whose idempotents form a subsemigroup." Bulletin of the Australian Mathematical Society 41, no. 2 (April 1990): 161–84. http://dx.doi.org/10.1017/s0004972700017986.

Full text

Abstract:

We prove that if the “type-II-construct” subsemigroup of a finite semigroup S is regular, then the “type-II” subsemigroup of S is computable (actually in this case, type-II and type-II-construct are equal). This, together with certain older results about pseudo-varieties of finite semigroups, leads to further results:(1) We get a new proof of Ash's theorem: If the idempotents in a finite semigroup S commute, then S divides a finite inverse semigroup. Equivalently: The pseudo-variety generated by the finite inverse semigroups consists of those finite semigroups whose idempotents commute.(2) We prove: If the idempotents of a finite semigroup S form a subsemigroup then S divides a finite orthodox semigroup. Equivalently: The pseudo-variety generated by the finite orthodox semigroups consists of those finite semigroups whose idempotents form a subsemigroup.(3) We prove: The union of all the subgroups of a semigroup S forms a subsemigroup if and only if 5 belongs to the pseudo-variety u * G if and only if Sn belongs to u. Here u denotes the pseudo-variety of finite semigroups which are unions of groups.For these three classes of semigroups, type-II is equal to type-II construct.

APA, Harvard, Vancouver, ISO, and other styles

5

VERNITSKI, ALEXEI. "ORDERED AND $\mathcal{J}$-TRIVIAL SEMIGROUPS AS DIVISORS OF SEMIGROUPS OF LANGUAGES." International Journal of Algebra and Computation 18, no. 07 (November 2008): 1223–29. http://dx.doi.org/10.1142/s021819670800486x.

Full text

Abstract:

A semigroup of languages is a set of languages considered with (and closed under) the operation of catenation. In other words, semigroups of languages are subsemigroups of power-semigroups of free semigroups. We prove that a (finite) semigroup is positively ordered if and only if it is a homomorphic image, under an order-preserving homomorphism, of a (finite) semigroup of languages. Hence it follows that a finite semigroup is [Formula: see text]-trivial if and only if it is a homomorphic image of a finite semigroup of languages.

APA, Harvard, Vancouver, ISO, and other styles

6

Almeida, J., M. H. Shahzamanian, and M. Kufleitner. "Nilpotency and strong nilpotency for finite semigroups." Quarterly Journal of Mathematics 70, no. 2 (November 21, 2018): 619–48. http://dx.doi.org/10.1093/qmath/hay059.

Full text

Abstract:

AbstractNilpotent semigroups in the sense of Mal’cev are defined by semigroup identities. Finite nilpotent semigroups constitute a pseudovariety, MN, which has finite rank. The semigroup identities that define nilpotent semigroups lead us to define strongly Mal’cev nilpotent semigroups. Finite strongly Mal’cev nilpotent semigroups constitute a non-finite rank pseudovariety, SMN. The pseudovariety SMN is strictly contained in the pseudovariety MN, but all finite nilpotent groups are in SMN. We show that the pseudovariety MN is the intersection of the pseudovariety BGnil with a pseudovariety defined by a κ-identity. We further compare the pseudovarieties MN and SMN with the Mal’cev product 𝖩ⓜ𝖦nill.

APA, Harvard, Vancouver, ISO, and other styles

7

Ash, C. J., and T. E. Hall. "Finite semigroups with commuting idempotents." Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics 43, no. 1 (August 1987): 81–90. http://dx.doi.org/10.1017/s1446788700028998.

Full text

Abstract:

AbstractWe show that every such semigroup is a homomorphic image of a subsemigroup of some finite inverse semigroup. This shows that the pseudovariety generated by the finite inverse semigroups consists of exactly the finite semigroups with commuting idempotents.

APA, Harvard, Vancouver, ISO, and other styles

8

IWAKI, E., E. JESPERS, S. O. JURIAANS, and A. C. SOUZA FILHO. "HYPERBOLICITY OF SEMIGROUP ALGEBRAS II." Journal of Algebra and Its Applications 09, no. 06 (December 2010): 871–76. http://dx.doi.org/10.1142/s0219498810004270.

Full text

Abstract:

In 1996, Jespers and Wang classified finite semigroups whose integral semigroup ring has finitely many units. In a recent paper, Iwaki–Juriaans–Souza Filho continued this line of research by partially classifying the finite semigroups whose rational semigroup algebra contains a ℤ-order with hyperbolic unit group. In this paper, we complete this classification and give an easy proof that deals with all finite semigroups.

APA, Harvard, Vancouver, ISO, and other styles

9

JACKSON, DAVID A. "DECISION AND SEPARABILITY PROBLEMS FOR BAUMSLAG–SOLITAR SEMIGROUPS." International Journal of Algebra and Computation 12, no. 01n02 (February 2002): 33–49. http://dx.doi.org/10.1142/s0218196702000857.

Full text

Abstract:

We show that the semigroups Sk,ℓ having semigroup presentations <a, b:abk = bℓ a> are residually finite and finitely separable. Generally, these semigroups have finite separating images which are finite groups and other finite separating images which are semigroups of order-increasing transformations on a finite partially ordered set. These semigroups thus have vastly different residual and separability properties than the Baumslag–Solitar groups which contain them.

APA, Harvard, Vancouver, ISO, and other styles

10

Dolinka, Igor, and Robert D. Gray. "Universal locally finite maximally homogeneous semigroups and inverse semigroups." Forum Mathematicum 30, no. 4 (July 1, 2018): 947–71. http://dx.doi.org/10.1515/forum-2017-0074.

Full text

Abstract:

Abstract In 1959, Philip Hall introduced the locally finite group {\mathcal{U}} , today known as Hall’s universal group. This group is countable, universal, simple, and any two finite isomorphic subgroups are conjugate in {\mathcal{U}} . It can explicitly be described as a direct limit of finite symmetric groups. It is homogeneous in the model-theoretic sense since it is the Fraïssé limit of the class of all finite groups. Since its introduction Hall’s group and several natural generalisations have been studied widely. In this article we use a generalisation of Fraïssé’s theory to construct a countable, universal, locally finite semigroup {\mathcal{T}} , that arises as a direct limit of finite full transformation semigroups, and has the highest possible degree of homogeneity. We prove that it is unique up to isomorphism among semigroups satisfying these properties. We prove an analogous result for inverse semigroups, constructing a maximally homogeneous universal locally finite inverse semigroup {\mathcal{I}} which is a direct limit of finite symmetric inverse semigroups (semigroups of partial bijections). The semigroups {\mathcal{T}} and {\mathcal{I}} are the natural counterparts of Hall’s universal group for semigroups and inverse semigroups, respectively. While these semigroups are not homogeneous, they still exhibit a great deal of symmetry. We study the structural features of these semigroups and locate several well-known homogeneous structures within them, such as the countable generic semilattice, the countable random bipartite graph, and Hall’s group itself.

APA, Harvard, Vancouver, ISO, and other styles

11

ARAÚJO, ISABEL M. "FINITE PRESENTABILITY OF SEMIGROUP CONSTRUCTIONS." International Journal of Algebra and Computation 12, no. 01n02 (February 2002): 19–31. http://dx.doi.org/10.1142/s0218196702000894.

Full text

Abstract:

We survey some recent results concerning finite presentability of several semigroup constructions. Namely we study direct products, wreath products, Rees matrix semigroups, Bruck–Reilly extensions, general products and strong semilattices of semigroups.

APA, Harvard, Vancouver, ISO, and other styles

12

Barnes, George R., Patricia B. Cerrito, and Inessa Levi. "Random walks on finite semigroups." Journal of Applied Probability 35, no. 4 (December 1998): 824–32. http://dx.doi.org/10.1239/jap/1032438378.

Full text

Abstract:

The purpose of this paper is to study the asymptotic properties of Markov chains on semigroups. In particular, the structure of transition matrices representing random walks on finite semigroups is examined. It is shown that the transition matrices associated with certain semigroups are block diagonal with identical blocks. The form of the blocks is determined via the algebraic structure of the semigroup.

APA, Harvard, Vancouver, ISO, and other styles

13

Barnes, George R., Patricia B. Cerrito, and Inessa Levi. "Random walks on finite semigroups." Journal of Applied Probability 35, no. 04 (December 1998): 824–32. http://dx.doi.org/10.1017/s0021900200016533.

Full text

Abstract:

The purpose of this paper is to study the asymptotic properties of Markov chains on semigroups. In particular, the structure of transition matrices representing random walks on finite semigroups is examined. It is shown that the transition matrices associated with certain semigroups are block diagonal with identical blocks. The form of the blocks is determined via the algebraic structure of the semigroup.

APA, Harvard, Vancouver, ISO, and other styles

14

Guo, Junying, and Xiaojiang Guo. "Algebras of right ample semigroups." Open Mathematics 16, no. 1 (August 3, 2018): 842–61. http://dx.doi.org/10.1515/math-2018-0075.

Full text

Abstract:

AbstractStrict RA semigroups are common generalizations of ample semigroups and inverse semigroups. The aim of this paper is to study algebras of strict RA semigroups. It is proved that any algebra of strict RA semigroups with finite idempotents has a generalized matrix representation whose degree is equal to the number of non-zero regular 𝓓-classes. In particular, it is proved that any algebra of finite right ample semigroups has a generalized upper triangular matrix representation whose degree is equal to the number of non-zero regular 𝓓-classes. As its application, we determine when an algebra of strict RA semigroups (right ample monoids) is semiprimitive. Moreover, we prove that an algebra of strict RA semigroups (right ample monoids) is left self-injective iff it is right self-injective, iff it is Frobenius, and iff the semigroup is a finite inverse semigroup.

APA, Harvard, Vancouver, ISO, and other styles

15

Okniński, Jan, and Mohan S. Putcha. "Embedding finite semigroup amalgams." Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics 51, no. 3 (December 1991): 489–96. http://dx.doi.org/10.1017/s1446788700034650.

Full text

Abstract:

AbstractLet S, T1,… Tk be finite semigroups and Ψ: S → Ti, be embeddings. When C[S] is semisimple, we find necessary and sufficient conditions for the semigroup amalgam (T1,…, Tk; S) to be embeddable in a finite semigroup. As a consequence we show that if S is a finite semigroup with C[S] semisimple, then S is an amalgamation base for the class of finite semigroups if and only if the principal ideals of S are linearly ordered. Our proof uses both the theory of representations by transformations and the theory of matrix representations as developed by Clifford, Munn and Ponizovskii

APA, Harvard, Vancouver, ISO, and other styles

16

FIRUZKUHY, A., and H. DOOSTIE. "Commuting Regularity degree of finite semigroups." Creative Mathematics and Informatics 24, no. 1 (2015): 43–47. http://dx.doi.org/10.37193/cmi.2015.01.05.

Full text

Abstract:

A pair (x, y) of elements x and y of a semigroup S is said to be a commuting regular pair, if there exists an element z ∈ S such that xy = (yx)z(yx). In a finite semigroup S, the probability that the pair (x, y) of elements of S is commuting regular will be denoted by dcr(S) and will be called the Commuting Regularity degree of S. Obviously if S is a group, then dcr(S) = 1. However for a semigroup S, getting an upper bound for dcr(S) will be of interest to study and to identify the different types of non-commutative semigroups. In this paper, we calculate this probability for certain classes of finite semigroups. In this study we managed to present an interesting class of semigroups where the probability is 1/2. This helps us to estimate a condition on non-commutative semigroups such that the commuting regularity of (x, y) yields the commuting regularity of (y, x).

APA, Harvard, Vancouver, ISO, and other styles

17

WEIL, PASCAL. "PROFINITE METHODS IN SEMIGROUP THEORY." International Journal of Algebra and Computation 12, no. 01n02 (February 2002): 137–78. http://dx.doi.org/10.1142/s0218196702000912.

Full text

Abstract:

Many recent results in finite semigroup theory make use of profinite methods, that is, they rely on the study of certain infinite, compact semigroups which arise as projective limits of finite semigroups. These ideas were introduced in semigroup theory in the 1980s, first to describe pseudovarieties in terms of so-called pseudo-identities: this is Reiterman's theorem, which can be viewed as the (much more complex) finite algebra analogue of Birkhoff's variety theorem. Soon, these methods were used in conjunction with virtually all the other approaches of finite semigroups, notably to study the decidability of product pseudovarieties. This paper surveys the contribution of profinite methods and the way they enriched and modified finite semigroup theory.

APA, Harvard, Vancouver, ISO, and other styles

18

MALTCEV, VICTOR. "CAYLEY AUTOMATON SEMIGROUPS." International Journal of Algebra and Computation 19, no. 01 (February 2009): 79–95. http://dx.doi.org/10.1142/s021819670900497x.

Full text

Abstract:

In this paper we characterize when a Cayley automaton semigroup is finite, is free, is a left zero semigroup, is a right zero semigroup, is a group, or is trivial. We also introduce dual Cayley automaton semigroups and discuss when they are finite.

APA, Harvard, Vancouver, ISO, and other styles

19

Jackson, Marcel. "Some undecidable embedding problems for finite semigroups." Proceedings of the Edinburgh Mathematical Society 42, no. 1 (February 1999): 113–25. http://dx.doi.org/10.1017/s0013091500020058.

Full text

Abstract:

Let S be a finite semigroup, A be a given subset of S and L, R, H, D and J be Green's equivalence relations. The problem of determining whether there exists a supersemigroup T of S from the class of all semigroups or from the class of finite semigroups, such that A lies in an L or R-class of T has a simple and well known solution (see for example [7], [8] or [3]). The analogous problem for J or D relations is trivial if T is of arbitrary size, but undecidable if T is required to be finite [4] (even if we restrict ourselves to the case |A| = 2 [6]). We show that for the relation H, the corresponding problem is undecidable in both the class of finite semigroups (answering Problem 1 of [9]) and in the class of all semigroups, extending related results obtained by M. V. Sapir in [9]. An infinite semigroup with a subset never lying in a H-class of any embedding semigroup is known and, in [9], the existence of a finite semigroup with this property is established. We present two eight element examples of such semigroups as well as other examples satisfying related properties.

APA, Harvard, Vancouver, ISO, and other styles

20

Liaqat, Iqra, and Wajeeha Younas. "SOME IMPORTANT APPLICATIONS OF SEMIGROUPS." Journal of Mathematical Sciences & Computational Mathematics 2, no. 2 (January 1, 2021): 317–21. http://dx.doi.org/10.15864/jmscm.2210.

Full text

Abstract:

This Paper deals with the some important applications of semigroups in general and regular semigroups in particular.The theory of finite semigroups has been of particular importance in theoretical computer science since the 1950s because of the natural link between finite semigroups and finite automata via the syntactic monoid. In probability theory, semigroups are associated with Markov process. In section 2 we have seen different areas of applications of semigroups. We identified some Applications in biology, Partial Differential equation, Formal Languages etc whose semigroup structures are nothing but regular.

APA, Harvard, Vancouver, ISO, and other styles

21

OLIJNYK, A. S., V. I. SUSHCHANSKY, and J. K. SLUPIK. "INVERSE SEMIGROUPS OF PARTIAL AUTOMATON PERMUTATIONS." International Journal of Algebra and Computation 20, no. 07 (November 2010): 923–52. http://dx.doi.org/10.1142/s0218196710005960.

Full text

Abstract:

The inverse semigroup of partial automaton permutations over a finite alphabet is characterized in terms of wreath products. The permutation conjugacy relation in this semigroup and the Green's relations are described. Criteria of primary conjugacy and conjugacy are given for certain naturally defined families of partial automaton permutations. Sufficient conditions under which an inverse semigroup admits a level transitive action are presented. We give explicit examples (monogenic inverse semigroups and some commutative Clifford semigroups) of inverse semigroups generated by finite automata.

APA, Harvard, Vancouver, ISO, and other styles

22

JONES, PETER R. "THE SEMIGROUPS B2 AND B0 ARE INHERENTLY NONFINITELY BASED, AS RESTRICTION SEMIGROUPS." International Journal of Algebra and Computation 23, no. 06 (September 2013): 1289–335. http://dx.doi.org/10.1142/s0218196713500264.

Full text

Abstract:

The five-element Brandt semigroup B2 and its four-element subsemigroup B0, obtained by omitting one nonidempotent, have played key roles in the study of varieties of semigroups. Regarded in that fashion, they have long been known to be finitely based. The semigroup B2 carries the natural structure of an inverse semigroup. Regarded as such, in the signature {⋅, -1}, it is also finitely based. It is perhaps surprising, then, that in the intermediate signature of restriction semigroups — essentially, "forgetting" the inverse operation x ↦ x-1 and retaining the induced operations x ↦ x+ = xx-1 and x ↦ x* = x-1x — it is not only nonfinitely based but inherently so (every locally finite variety that contains it is also nonfinitely based). The essence of the nonfinite behavior is actually exhibited in B0, which carries the natural structure of a restriction semigroup, inherited from B2. It is again inherently nonfinitely based, regarded in that fashion. It follows that any finite restriction semigroup on which the two unary operations do not coincide is nonfinitely based. Therefore for finite restriction semigroups, the existence of a finite basis is decidable "modulo monoids". These results are consequences of — and discovered as a result of — an analysis of varieties of "strict" restriction semigroups, namely those generated by Brandt semigroups and, more generally, of varieties of "completely r-semisimple" restriction semigroups: those semigroups in which no comparable projections are related under the generalized Green relation 𝔻. For example, explicit bases of identities are found for the varieties generated by B0 and B2.

APA, Harvard, Vancouver, ISO, and other styles

23

Easdown, D., and W. D. Munn. "On semigroups with involution." Bulletin of the Australian Mathematical Society 48, no. 1 (August 1993): 93–100. http://dx.doi.org/10.1017/s0004972700015495.

Full text

Abstract:

A semigroup S with an involution * is called a special involution semigroup if and only if, for every finite nonempty subset T of S,.It is shown that a semigroup is inverse if and only if it is a special involution semigroup in which every element invariant under the involution is periodic. Other examples of special involution semigroups are discussed; these include free semigroups, totally ordered cancellative commutative semigroups and certain semigroups of matrices. Some properties of the semigroup algebras of special involution semigroups are also derived. In particular, it is shown that their real and complex semigroup algebras are semiprimitive.

APA, Harvard, Vancouver, ISO, and other styles

24

RHODES, JOHN, and BENJAMIN STEINBERG. "PROFINITE SEMIGROUPS, VARIETIES, EXPANSIONS AND THE STRUCTURE OF RELATIVELY FREE PROFINITE SEMIGROUPS." International Journal of Algebra and Computation 11, no. 06 (December 2001): 627–72. http://dx.doi.org/10.1142/s0218196701000784.

Full text

Abstract:

Building on the now generally accepted thesis that profinite semigroups are important to the study of finite semigroups, this paper proposes to apply various of the techniques, already used in studying algebraic semigroups, to profinite semigroups. The goal in mind is to understand free profinite semigroups on a finite set. To do this we define profinite varieties. We then introduce expansions of profinite semigroups, giving examples of several classes of such expansions. These expansions will then be useful in studying various structural properties of relatively free profinite semigroups, since these semigroups will be fixed points of certain expansions. This study also requires a look at profinite categories, semigroupoids, and Cayley graphs, all of which we handle in turn. We also study the structure of the minimal ideal of relatively free profinite semigroups showing, in particular, that the minimal ideal of the free profinite semigroup on a finite set with more than two generators is not a relatively free profinite completely simple semigroup, as well as some generalizations to related pseudovarieties.

APA, Harvard, Vancouver, ISO, and other styles

25

Guo, Junying, and Xiaojiang Guo. "Self-injectivity of semigroup algebras." Open Mathematics 18, no. 1 (May 26, 2020): 333–52. http://dx.doi.org/10.1515/math-2020-0023.

Full text

Abstract:

Abstract It is proved that for an IC abundant semigroup (a primitive abundant semigroup; a primitively semisimple semigroup) S and a field K, if K 0[S] is right (left) self-injective, then S is a finite regular semigroup. This extends and enriches the related results of Okniński on self-injective algebras of regular semigroups, and affirmatively answers Okniński’s problem: does that a semigroup algebra K[S] is a right (respectively, left) self-injective imply that S is finite? (Semigroup Algebras, Marcel Dekker, 1990), for IC abundant semigroups (primitively semisimple semigroups; primitive abundant semigroups). Moreover, we determine the structure of K 0[S] being right (left) self-injective when K 0[S] has a unity. As their applications, we determine some sufficient and necessary conditions for the algebra of an IC abundant semigroup (a primitively semisimple semigroup; a primitive abundant semigroup) over a field to be semisimple.

APA, Harvard, Vancouver, ISO, and other styles

26

JACKSON, MARCEL, and RALPH McKENZIE. "INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS." International Journal of Algebra and Computation 16, no. 01 (February 2006): 119–40. http://dx.doi.org/10.1142/s0218196706002846.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

27

Laan, Valdis, and Ülo Reimaa. "Morita equivalence of factorizable semigroups." International Journal of Algebra and Computation 29, no. 04 (June 2019): 723–41. http://dx.doi.org/10.1142/s0218196719500243.

Full text

Abstract:

A semigroup is called factorizable if each of its elements can be written as a product. We study equivalences and adjunctions between various categories of acts over a fixed factorizable semigroup. We prove that two factorizable semigroups are Morita equivalent if and only if they are strongly Morita equivalent. We also show that Morita equivalence of finite factorizable semigroups is algorithmically decidable in finite time.

APA, Harvard, Vancouver, ISO, and other styles

28

Shirazi, Zadeh, and Nasser Golestani. "On classifications of transformation semigroups: Indicator sequences and indicator topological spaces." Filomat 26, no. 2 (2012): 313–29. http://dx.doi.org/10.2298/fil1202313s.

Full text

Abstract:

In this paper considering a transformation semigroup with finite height we define the notion of indicator sequence in such a way that any two transformation semigroups with the same indicator sequence have the same height. Also related to any transformation semigroup a topological space, called indicator topological space, is defined in such a way that transformation semigroups with homeomorphic indicator topological spaces have the same height. Moreover any two transformation semigroups with homeomorphic indicator topological spaces and finite height have the same indicator sequences.

APA, Harvard, Vancouver, ISO, and other styles

29

KAMBITES, MARK. "ON THE KROHN–RHODES COMPLEXITY OF SEMIGROUPS OF UPPER TRIANGULAR MATRICES." International Journal of Algebra and Computation 17, no. 01 (February 2007): 187–201. http://dx.doi.org/10.1142/s0218196707003548.

Full text

Abstract:

We consider the Krohn–Rhodes complexity of certain semigroups of upper triangular matrices over finite fields. We show that for any n > 1 and finite field k, the semigroups of all n × n upper triangular matrices over k and of all n × n unitriangular matrices over k have complexity n - 1. A consequence is that the complexity c > 1 of a finite semigroup places a lower bound of c + 1 on the dimension of any faithful triangular representation of that semigroup over a finite field.

APA, Harvard, Vancouver, ISO, and other styles

30

Muradov, F. Kh. "Ternary semigroups of topological transformations." BULLETIN OF THE KARAGANDA UNIVERSITY-MATHEMATICS 102, no. 2 (June 30, 2021): 84–91. http://dx.doi.org/10.31489/2021m2/84-91.

Full text

Abstract:

A ternary semigroup is a nonempty set with a ternary operation which is associative. The purpose of the present paper is to give a characterization of open sets of finite-dimensional Euclidean spaces by ternary semigroups of pairs of homeomorphic transformations and extend to ternary semigroups certain results of L.M. Gluskin concerned with semigroups of homeomorphic transformations of finite-dimensional Euclidean spaces.

APA, Harvard, Vancouver, ISO, and other styles

31

RODARO, EMANUELE. "BICYCLIC SUBSEMIGROUPS IN AMALGAMS OF FINITE INVERSE SEMIGROUPS." International Journal of Algebra and Computation 20, no. 01 (February 2010): 89–113. http://dx.doi.org/10.1142/s021819671000556x.

Full text

Abstract:

It is well known that an inverse semigroup is completely semisimple if and only if it does not contain a copy of the bicyclic semigroup. We characterize the amalgams [S1, S2; U] of two finite inverse semigroups S1, S2whose free product with amalgamation is completely semisimple and we show that checking whether the amalgamated free product of finite inverse semigroups contains a bicyclic subsemigroup is decidable by means of a polynomial time algorithm with respect to max {|S1|,|S2|}. Moreover we consider amalgams of finite inverse semigroups respecting the [Formula: see text]-order proving that the free product with amalgamation is completely semisimple and we also provide necessary and sufficient conditions for the [Formula: see text]-classes to be finite.

APA, Harvard, Vancouver, ISO, and other styles

32

JACKSON, MARCEL. "DUALISABILITY OF FINITE SEMIGROUPS." International Journal of Algebra and Computation 13, no. 04 (August 2003): 481–97. http://dx.doi.org/10.1142/s0218196703001535.

Full text

Abstract:

We describe the inherently non-dualisable finite algebras from some semigroup related classes. The classes for which this problem is solved include the variety of bands, the pseudovariety of aperiodic monoids, commutative monoids, and (assuming a reasonable conjecture in the literature) the varieties of all finite monoids and finite inverse semigroups. The first example of an inherently non-dualisable entropic algebra is also presented.

APA, Harvard, Vancouver, ISO, and other styles

33

Brzozowski, Janusz, and Marek Szykuła. "Large Aperiodic Semigroups." International Journal of Foundations of Computer Science 26, no. 07 (November 2015): 913–31. http://dx.doi.org/10.1142/s0129054115400067.

Full text

Abstract:

We search for the largest syntactic semigroups of star-free languages having n left quotients; equivalently, we look for the largest transition semigroups of aperiodic finite automata with n states. We first introduce unitary semigroups generated by transformations that change only one state. In particular, we study unitary-complete semigroups which have a special structure, and show that each maximal unitary semigroup is unitary-complete. For [Formula: see text] we exhibit a unitary-complete semigroup that is larger than any aperiodic semigroup known to date. We then present even larger aperiodic semigroups, generated by transformations that map a non-empty subset of states to a single state; we call such transformations and semigroups semiconstant. We examine semiconstant tree semigroups which have a structure based on full binary trees. The semiconstant tree semigroups are at present the best candidates for largest aperiodic semigroups.

APA, Harvard, Vancouver, ISO, and other styles

34

LAWSON, M. V. "NON-COMMUTATIVE STONE DUALITY: INVERSE SEMIGROUPS, TOPOLOGICAL GROUPOIDS AND C*-ALGEBRAS." International Journal of Algebra and Computation 22, no. 06 (August 31, 2012): 1250058. http://dx.doi.org/10.1142/s0218196712500580.

Full text

Abstract:

We study a non-commutative generalization of Stone duality that connects a class of inverse semigroups, called Boolean inverse ∧-semigroups, with a class of topological groupoids, called Hausdorff Boolean groupoids. Much of the paper is given over to showing that Boolean inverse ∧-semigroups arise as completions of inverse ∧-semigroups we call pre-Boolean. An inverse ∧-semigroup is pre-Boolean if and only if every tight filter is an ultrafilter, where tight filters are defined by combining ideas of both Exel and Lenz. A simple necessary condition for a semigroup to be pre-Boolean is derived and a variety of examples of inverse semigroups are shown to satisfy it. Thus the polycyclic inverse monoids, and certain Rees matrix semigroups over the polycyclics, are pre-Boolean and it is proved that the groups of units of their completions are precisely the Thompson–Higman groups Gn, r. The inverse semigroups arising from suitable directed graphs are also pre-Boolean and the topological groupoids arising from these graph inverse semigroups under our non-commutative Stone duality are the groupoids that arise from the Cuntz–Krieger C*-algebras. An elementary application of our theory shows that the finite, fundamental Boolean inverse ∧-semigroups are just the finite direct products of finite symmetric inverse monoids. Finally, we explain how tight filters are related to prime filters setting the scene for future work.

APA, Harvard, Vancouver, ISO, and other styles

35

Umar, A., and M. M. Zubairu. "On certain semigroups of contraction mappings of a finite chain." Algebra and Discrete Mathematics 32, no. 2 (2021): 299–320. http://dx.doi.org/10.12958/adm1816.

Full text

Abstract:

Let[n] ={1,2, . . . , n} be a finite chain and let Pn (resp.,Tn) be the semigroup of partial transformations on[n] (resp., full transformations on[n]). Let CPn={α∈ Pn: (for allx, y ∈ Dom α)|xα−yα|⩽|x−y|}(resp., CTn={α∈ Tn: (for allx, y∈[n])|xα−yα|⩽|x−y|}) be the subsemigroup of partial contractionmappings on[n](resp., subsemigroup of full contraction mappingson[n]). We characterize all the starred Green’s relations on C Pn and it subsemigroup of order preserving and/or order reversingand subsemigroup of order preserving partial contractions on[n], respectively. We show that the semigroups CPn and CTn, and some of their subsemigroups are left abundant semigroups for all n but not right abundant forn⩾4. We further show that the set ofregular elements of the semigroup CTn and its subsemigroup of order preserving or order reversing full contractions on[n], each formsa regular subsemigroup and an orthodox semigroup, respectively.

APA, Harvard, Vancouver, ISO, and other styles

36

Clayton, Ashley. "On finitary properties for fiber products of free semigroups and free monoids." Semigroup Forum 101, no. 2 (August 14, 2020): 326–57. http://dx.doi.org/10.1007/s00233-020-10127-0.

Full text

Abstract:

Abstract We consider necessary and sufficient conditions for finite generation and finite presentability for fiber products of free semigroups and free monoids. We give a necessary and sufficient condition on finite fiber quotients for a fiber product of two free monoids to be finitely generated, and show that all such fiber products are also finitely presented. By way of contrast, we show that fiber products of free semigroups over finite fiber quotients are never finitely generated. We then consider fiber products of free semigroups over infinite semigroups, and show that for such a fiber product to be finitely generated, the quotient must be infinite but finitely generated, idempotent-free, and $$\mathcal {J}$$ J -trivial. Finally, we construct automata accepting the indecomposable elements of the fiber product of two free monoids/semigroups over free monoid/semigroup fibers, and give a necessary and sufficient condition for such a product to be finitely generated.

APA, Harvard, Vancouver, ISO, and other styles

37

Ayyash, Mohammed Abu, and Alessandra Cherubini. "Some completely semisimple HNN-extensions of inverse semigroups." International Journal of Algebra and Computation 30, no. 02 (October 18, 2019): 217–43. http://dx.doi.org/10.1142/s0218196719500711.

Full text

Abstract:

We give necessary and sufficient conditions in order that lower bounded HNN-extensions of inverse semigroups and HNN-extensions of finite inverse semigroups are completely semisimple semigroups. Since it is well known that an inverse semigroup is completely semisimple if and only if it does not contain a copy of the bicyclic semigroup, we first characterize such HNN-extensions containing a bicyclic subsemigroup making use of the special feature of their Schützenberger automata.

APA, Harvard, Vancouver, ISO, and other styles

38

Lee, Edmond W. H., John Rhodes, and Benjamin Steinberg. "Join irreducible semigroups." International Journal of Algebra and Computation 29, no. 07 (October 23, 2019): 1249–310. http://dx.doi.org/10.1142/s0218196719500498.

Full text

Abstract:

We begin a systematic study of finite semigroups that generate join irreducible members of the lattice of pseudovarieties of finite semigroups, which are important for the spectral theory of this lattice. Finite semigroups [Formula: see text] that generate join irreducible pseudovarieties are characterized as follows: whenever [Formula: see text] divides a direct product [Formula: see text] of finite semigroups, then [Formula: see text] divides either [Formula: see text] or [Formula: see text] for some [Formula: see text]. We present a new operator [Formula: see text] that preserves the property of join irreducibility, as does the dual operator, and show that iteration of these operators on any nontrivial join irreducible pseudovariety leads to an infinite hierarchy of join irreducible pseudovarieties. We also describe all join irreducible pseudovarieties generated by a semigroup of order up to five. It turns out that there are [Formula: see text] such pseudovarieties, and there is a relatively easy way to remember them. In addition, we survey most results known about join irreducible pseudovarieties to date and generalize a number of results in Sec. 7.3 of [The[Formula: see text]-theory of Finite Semigroups, Springer Monographs in Mathematics (Springer, Berlin, 2009)].

APA, Harvard, Vancouver, ISO, and other styles

39

Banakh, Iryna, Taras Banakh, and Serhii Bardyla. "A Semigroup Is Finite Iff It Is Chain-Finite and Antichain-Finite." Axioms 10, no. 1 (January 16, 2021): 9. http://dx.doi.org/10.3390/axioms10010009.

Full text

Abstract:

A subset A of a semigroup S is called a chain (antichain) if ab∈{a,b} (ab∉{a,b}) for any (distinct) elements a,b∈A. A semigroup S is called periodic if for every element x∈S there exists n∈N such that xn is an idempotent. A semigroup S is called (anti)chain-finite if S contains no infinite (anti)chains. We prove that each antichain-finite semigroup S is periodic and for every idempotent e of S the set e∞={x∈S:∃n∈N(xn=e)} is finite. This property of antichain-finite semigroups is used to prove that a semigroup is finite if and only if it is chain-finite and antichain-finite. Furthermore, we present an example of an antichain-finite semilattice that is not a union of finitely many chains.

APA, Harvard, Vancouver, ISO, and other styles

40

JESPERS, E., and M. H. SHAHZAMANIAN. "A DESCRIPTION OF A CLASS OF FINITE SEMIGROUPS THAT ARE NEAR TO BEING MAL'CEV NILPOTENT." Journal of Algebra and Its Applications 12, no. 05 (May 7, 2013): 1250221. http://dx.doi.org/10.1142/s0219498812502210.

Full text

Abstract:

In this paper we continue the investigation on the algebraic structure of a finite semigroup S that is determined by its associated upper non-nilpotent graph [Formula: see text]. The vertices of this graph are the elements of S and two vertices are adjacent if they generate a semigroup that is not nilpotent (in the sense of Mal'cev). We introduce a class of semigroups in which the Mal'cev nilpotent property lifts through ideal chains. We call this the class of pseudo-nilpotent semigroups. The definition is such that the global information that a semigroup is not nilpotent induces local information, i.e. some two-generated subsemigroups are not nilpotent. It turns out that a finite monoid (in particular, a finite group) is pseudo-nilpotent if and only if it is nilpotent. Our main result is a description of pseudo-nilpotent finite semigroups S in terms of their associated graph [Formula: see text]. In particular, S has a largest nilpotent ideal, say K, and S/K is a 0-disjoint union of its connected components (adjoined with a zero) with at least two elements.

APA, Harvard, Vancouver, ISO, and other styles

41

Preston, G. B. "Monogenic inverse semigroups." Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics 40, no. 3 (June 1986): 321–42. http://dx.doi.org/10.1017/s1446788700027543.

Full text

Abstract:

AbstractWe give a survey of some of the realisations that have been given of monogenic inverse semigroups and discuss their relation to one another. We then analyse the representations by bijections, combined under composition, of monogenic inverse semigroups, and classify these into isomorphism types. This provides a particularly easy way of classifying monogenic inverse semigroups into isomorphism types. Of interest is that we find two quite distinct representations by bijections of free monogenic inverse semigroups and show that all such representations must contain one of these two representations. We call a bijection of the form ai ↦ ai+1, i = 1,2,…, r − 1, a finite link of length r, and one of the form ai ↦ ai+1, i = 1,2…, a forward link. The inverse of a forward link we call a backward link. Two bijections u: A → B and r: C → D are said to be strongly disjoint if A ∩ C, A ∩ D, B ∩ C and B ∩ D are each empty. The two distinct representations of a free monogenic inverse semigroup, that we have just referred to, are first, such that its generator is the union of a counbtable set os finite links that are pairwise storongly disjoint part of any representation of a free monogenic inverse semigroup, the remaining part not affecting the isomorphism type. Each representation of a monogenic inverse semigroup that is not free contains a strongly disjoint part, determining it to within isomorphism, that is generated by either the strongly disjoint union of a finite link and a permutation or the strongly disjoint union of a finite and a forward link.

APA, Harvard, Vancouver, ISO, and other styles

42

CAIN, ALAN J., NIK RUŠKUC, and RICHARD M. THOMAS. "UNARY FA-PRESENTABLE SEMIGROUPS." International Journal of Algebra and Computation 22, no. 04 (June 2012): 1250038. http://dx.doi.org/10.1142/s0218196712500385.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

43

KAMBITES, MARK. "PRESENTATIONS FOR SEMIGROUPS AND SEMIGROUPOIDS." International Journal of Algebra and Computation 15, no. 02 (April 2005): 291–308. http://dx.doi.org/10.1142/s0218196705002268.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

44

Ayik, H., and N. Ruškuc. "Generators and relations of Rees matrix semigroups." Proceedings of the Edinburgh Mathematical Society 42, no. 3 (October 1999): 481–95. http://dx.doi.org/10.1017/s0013091500020472.

Full text

Abstract:

In this paper we consider finite generation and finite presentability of Rees matrix semigroups (with or without zero) over arbitrary semigroups. The main result states that a Rees matrix semigroup M[S; I, J; P] is finitely generated (respectively, finitely presented) if and only if S is finitely generated (respectively, finitely presented), and the sets I, J and S\U are finite, where U is the ideal of S generated by the entries of P.

APA, Harvard, Vancouver, ISO, and other styles

45

Giraldes, Emilia, and John M. Howie. "Semigroups of high rank." Proceedings of the Edinburgh Mathematical Society 28, no. 1 (February 1985): 13–34. http://dx.doi.org/10.1017/s0013091500003163.

Full text

Abstract:

By the rank r(S) of a finite semigroup S we shall mean the minimum cardinality of a set of generators ofS. For a group G, as remarked in [3], one has r(G)≦log2|G|, the bound being attained when G is an elementary abelian 2-group. By contrast, we shall see that there exist finite semigroups S for which r(S)≧|S| – 1. In the hope that it will not be considered too whimsical, we shall refer to a finite semigroup S of maximal rank (i.e. for which r(S) = |S|) as royal; a semigroup of next-to-maximal rank (i.e. for which r(S) = |S|–1) will be called noble.

APA, Harvard, Vancouver, ISO, and other styles

46

Giraldes, Emilia, and John M. Howie. "Embeddings into finite idempotent-generated semigroups: some arithmetical results." Proceedings of the Edinburgh Mathematical Society 34, no. 2 (June 1991): 259–69. http://dx.doi.org/10.1017/s0013091500007161.

Full text

Abstract:

A semiband is defined as a semigroup generated by idempotents. It is known that every finite semigroup is embeddable in a finite semiband. For a class C of semigroups and an integer n≧2, the number σC (n) is defined as the smallest k with the property that every semigroup of order n in the class C is embeddable in a semiband of order not exceeding k. It is shown that for the class Gp of groups σGp(n) = nq(ρGp(n)), whereandEstimates are known (and are quoted) for the function q. Estimates are considered for the function pC for various CIt is shown also that if C0S, CS denote respectively the classes of completely 0-simple and completely simple semigroups, then

APA, Harvard, Vancouver, ISO, and other styles

47

Bulatov, Andrei, Marcin Kozik, Peter Mayr, and Markus Steindl. "The subpower membership problem for semigroups." International Journal of Algebra and Computation 26, no. 07 (November 2016): 1435–51. http://dx.doi.org/10.1142/s0218196716500612.

Full text

Abstract:

Fix a finite semigroup [Formula: see text] and let [Formula: see text] be tuples in a direct power [Formula: see text]. The subpower membership problem (SMP) asks whether [Formula: see text] can be generated by [Formula: see text]. If [Formula: see text] is a finite group, then there is a folklore algorithm that decides this problem in time polynomial in [Formula: see text]. For semigroups this problem always lies in PSPACE. We show that the [Formula: see text] for a full transformation semigroup on [Formula: see text] or more letters is actually PSPACE-complete, while on [Formula: see text] letters it is in P. For commutative semigroups, we provide a dichotomy result: if a commutative semigroup [Formula: see text] embeds into a direct product of a Clifford semigroup and a nilpotent semigroup, then [Formula: see text] is in P; otherwise it is NP-complete.

APA, Harvard, Vancouver, ISO, and other styles

48

Campbell, C. M., E. F. Robertson, N. Ruškuc, and R. M. Thomas. "On semigroups defined by Coxeter-type presentations." Proceedings of the Royal Society of Edinburgh: Section A Mathematics 125, no. 5 (1995): 1063–75. http://dx.doi.org/10.1017/s0308210500022642.

Full text

Abstract:

Presentations of Coxeter type are defined for semigroups. Minimal right ideals of a semigroup defined by such a presentation are proved to be isomorphic to the group with the same presentation. A necessary and sufficient condition for these semigroups to be finite is found. The structure of semigroups defined by Coxeter-type presentations for the symmetric and alternating groups is examined in detail.

APA, Harvard, Vancouver, ISO, and other styles

49

Auinger, Karl. "Residual finiteness of free products of combinatorial strict inverse semigroups." Proceedings of the Royal Society of Edinburgh: Section A Mathematics 124, no. 1 (1994): 137–47. http://dx.doi.org/10.1017/s0308210500029243.

Full text

Abstract:

It is shown that the free product of two residually finite combinatorial strict inverse semigroups in general is not residually finite. In contrast, the free product of a residually finite combinatorial strict inverse semigroup and a semilattice is residually finite.

APA, Harvard, Vancouver, ISO, and other styles

50

DOMBI, E. R., and N. D. GILBERT. "THE TILING SEMIGROUPS OF ONE-DIMENSIONAL PERIODIC TILINGS." Journal of the Australian Mathematical Society 87, no. 2 (July 23, 2009): 153–60. http://dx.doi.org/10.1017/s144678870800075x.

Full text

Abstract:

AbstractA one-dimensional tiling is a bi-infinite string on a finite alphabet, and its tiling semigroup is an inverse semigroup whose elements are marked finite substrings of the tiling. We characterize the structure of these semigroups in the periodic case, in which the tiling is obtained by repetition of a fixed primitive word.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!