A certain synchronizing property of subshifts and flow equivalence

We will study a certain synchronizing property of subshifts called λ-synchronization. The λ-synchronizing subshifts form a large class of irreducible subshifts containing irreducible sofic shifts. We prove that the λ-synchronization is invariant under flow equivalence of subshifts. The λ-synchronizing K-groups and the λ-synchronizing Bowen-Franks groups are studied and proved to be invariant under flow equivalence of λ-synchronizing subshifts. They are new flow equivalence invariants for λ-synchronizing subshifts.     

On the finite basis problem for certain 2-limited words

Let X* be a free monoid over an alphabet X and W be a finite language over X. Let S(W) be the Rees quotient X*/I(W), where I(W) is the ideal of X* consisting of all elements of X* that are not subwords of W. Then S(W) is a finite monoid with zero and is called the discrete syntactic monoid of W. W is called finitely based if the monoid S(W) is finitely based. In this paper, we give some sufficient conditions for a monoid to be non-finitely based. Using these conditions and other results, we describe all finitely based 2-limited words over a three-element alphabet. Furthermore, an explicit algorithm is given to decide that whether or not a 2-limited word in which there are exactly two non-linear letters is finitely based.     

Fundamental groups,inverse schützenberger automata,and monoid presentations

This paper gives decidable conditions for when a finitely generated subgroup of a free group is the fundamental group of a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Also, generalizations are given to specific types of inverse monoids as well as to monoids which are "nearly inverse." This result has applications to computing membership for inverse monoids in a Mal'cev product of the pseudovariety of semilattices with a pseudovariety of groups.

This paper also shows that there is a bijection between strongly connected inverse automata and subgroups of a free group, generated by positive words. Hence, we also obtain that it is decidable whether a finite strongly connected inverse automaton is a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Again, we have generalizations to other types of inverse monoids and to "nearly inverse" monoids. We show that it is undecidable whether a finite strongly connected inverse automaton is a Schützenberger automaton of a monoid presentation of anE-unitary inverse monoid.     

Lifting covers of sofic shifts

We define a class of factor maps between sofic shifts, called lifting maps, which generalize the closing maps. We show that an irreducible sofic shiftS has only finitely manyS-conjugacy classes of minimal left (or right) lifting covers. The number of these classes is a computable conjugacy invariant ofS. Furthermore, every left lifting cover factors through a minimal left lifting cover.     

The Congruence Lattice of Bruck–Reilly Extensions

We study the lattice. C(S) of congruences of a monoid S which is the Bruck-Reilly extension of a monoid T by a homomorphism . The inclusion, meet and join of congruences are described in terms of congruences and ideals of T. We show that C(S) can be naturally decomposed into three sublattices, corresponding (roughly speaking) to the three different types of congruences on such semigroups.1991 Mathematics Subject Classification: 20M10     

Sur les automates qui reconnaissent une famille de langages

The main results about automatas and the languages they accept are easily extended to automatas which recognize a family of languages (L_i)_iεI of a free monoid, that is to automatas which recognize simultaneously all the languages L_i. This generalization enhances the notion of automata of type (p,r) introduced by S. Eilenberg [4]. In a similar way the notion of syntactic monoid of a family of languages extends the notion of syntactic monoid of a language. This extension is far from being trivial since we show that every finite monoid is the syntactic monoid of a recognizable partition of a free monoid, though this is false for the syntactic monoids of languages.      

Cycles of relatively prime length and the road coloring problem

We give a partial answer to theroad coloring problem, a purely graphtheoretical question with applications in both symbolic dynamics and automata theory. The question is whether for any positive integerk and for any aperiodic and strongly connected graphG with all vertices of out-degreek, we can labelG with symbols in an alphabet ofk letters so that all the edges going out from a vertex take a different label and all paths inG presenting a wordW terminate at the same vertex, for someW. Such a labelling is calledsynchronizing coloring ofG. Anyaperiodic graphG contains a setS of cycles where the greatest common divisor of the lengths equals 1. We establish some geometrical conditions onS to ensure the existence of a synchronizing coloring.     

Principal Weak Flatness and Regularity of Diagonal Acts

For a monoid S, the set S × S equipped with the componentwise right S-action is called the diagonal act of S and is denoted by D(S). A monoid S is a left PP (left PSF) monoid if every principal left ideal of S is projective (strongly flat). We shall call a monoid S left P(P) if all principal left ideals of S satisfy condition (P). We shall call a monoid S weakly left P(P) monoid if the equalities as = bs, xb = yb in S imply the existence of r ∈ S such that xar = yar, rs = s. In this article, we prove that a monoid S is left PSF if and only if S is (weakly) left P(P) and D(S) is principally weakly flat. We provide examples showing that the implications left PSF ? left P(P) ? weakly left P(P) are strict. Finally, we investigate regularity of diagonal acts D(S), and we prove that for a right PP monoid S the diagonal act D(S) is regular if and only if every finite product of regular acts is regular. Furthermore, we prove that for a full transformation monoid S = 𝒯 _X , D(S) is regular.     

Retracts and monomorphism monoids in semigroup varieties

If a semigroup varietyV contains the variety of commutative three-nilpotent semigroups, or if it is a variety of bands containing all semilattices, then, for anyA∈V and any left cancellative monoidM, there is a semigroupS∈V such thatA is a retract ofS andM is isomorphic to the monoid of all injective endomorphisms ofS.     

Weakly Integrally Closed Numerical Monoids and Forbidden Patterns

An integral domain D is weakly integrally closed if whenever x is in the quotient field of D, and J is a nonzero finitely generated ideal of D such that xJ ? J ², then x is in D. We define weakly integrally closed (WIC) numerical monoids similarly. If a monoid algebra is weakly integrally closed, then so is the monoid. The characteristic function of a numerical monoid M can be thought of as an infinite binary string s(M). A pattern of finitely many 0's and 1's is called forbidden if whenever s(M) contains it, then M is not weakly integrally closed. The pattern 11011 is forbidden. We show that a numerical monoid M is WIC if and only if s(M) contains no forbidden patterns. We also show that for every finite set S of forbidden patterns, there exists a numerical monoid M that is not WIC and for which s(M) contains no stretch (in a natural sense) of a pattern in S.     

A minimal 0–1 subshift with noncompact set of ergodic measures

Summary By a minimal 0–1 subshift we mean a pair (X, S), where S denotes the left shift on C={0, 1}^z and X is a minimal compact S-invariant subset of C. Developing some of the methods of Williams [2] of obtaining not uniquely ergodic minimal subshifts we construct such a subshift, for which the set of all ergodic measures is noncompact for the weak^* topology. In other words, the Choquet simplex of all invariant measures of the subshift is not a Bauer simplex.     

A Note on Prehomomorphisms

We show that if G is a free group with basis X then any map θ from X to an inverse monoid S extends to a monoid prehomomorphism ψ: G\rightarrow S. As an application we give an affirmative answer to a problem of M. Petrich. 1980 Mathematics Subject Classification: Primary 20M10. September 14, 1999     

Monoids over which all strongly flat left acts are regular

Let Sbe a monoid. It is shown that all strongly flat left S-acts are regular if and only if all left S-acts having the property (E) are regular if and only if Sis a left PP monoid and satisfies (FP₂).This result answers a question in Kilp and Knauer [5].     

Delta Sets of Numerical Monoids Using Nonminimal Sets of Generators

Several recent articles have studied the structure of the delta set of a numerical monoid. We continue this work with the assumption that the generating set S chosen for the numerical monoid M is not necessarily minimal. We show that for certain choices of S, the resulting delta set can be made (in terms of cardinality) arbitrarily large or small. We close with a close analysis of the case where M =?n ₁, n ₂, in ₁ + jn ₂?for non-negative i and j.     

An order topologyfor finitely generated free monoids

In this article a method is given for embedding a finitely generated free monoid as a dense subset of the unit interval. This gives an order topology for the monoid such that the submonoids generated by an important class of maximal codes occur as “thick” subsets. As an ordered topological space, the notion of thickness in a frec monoid can be interpreted in a number of ways. One such notion is that of density. In particular, subsets of a free monoid that fail to meet all two sided ideals (the thin sets, of which recognizable codes are an example) are shown (corollary 4.2) to be nowhere dense. Furthermore, it is shown (corollary 5.1) that a thin code is maximal if and only if the submonoid that it generates is dense on some interval. Thus thin codes that are maximal are precisely those that generate thick submonoids. Another notion of thickness is that of category. The embedding allows the free monoid to be viewed as a subspace of the unit interval. In theorem 5.6 it is shown that a thin code is maximal just in case the closure of the submonoid that it generates is second category in the unit interval. A mild connection with Lebesque measure is then made. In what follows, all free monoids are assumed to be generated by a finite set of at least two elements. IfA is such a set, thenA ^* denotes the free monoid generated byA. The setA is called an alphabet, the elements ofA ^* are called words, ande denotes the empty word inA ^*. Topological terminology and notation follows that of Kelley [2].     

Monoids and Groups of <Emphasis Type="Italic">I</Emphasis>-Type

A monoid S generated by {x₁,. . .,x_n} is said to be of (left) I-type if there exists a map v from the free Abelian monoid FaM_n of rank n generated by {u₁,. . .,u_n} to S so that for all a∈FaM_n one has {v(u₁a),. . .,v(u_na)}={x₁v(a),. . .,x_nv(a)}. Then S has a group of fractions, which is called a group of (left) I-type. These monoids first appeared in the work of Gateva-Ivanova and Van den Bergh, inspired by earlier work of Tate and Van den Bergh. In this paper we show that monoids and groups of left I-type can be characterized as natural submonoids and groups of semidirect products of the free Abelian group Fa_n and the symmetric group of degree n. It follows that these notions are left–right symmetric. As a consequence we determine many aspects of the algebraic structure of such monoids and groups. In particular, they can often be decomposed as products of monoids and groups of the same type but on less generators and many such groups are poly-infinite cyclic. We also prove that the minimal prime ideals of a monoid S of I-type, and of the corresponding monoid algebra, are principal and generated by a normal element. Further, via left–right divisibility, we show that all semiprime ideals of S can be described. The latter yields an ideal chain of S with factors that are semigroups of matrix type over cancellative semigroups. In memory of Paul Wauters Mathematics Subject Classifications (2000) 20F05, 20M05; 16S34, 16S36, 20F16. The authors were supported in part by Onderzoeksraad of Vrije Universiteit Brussel, Fonds voor Wetenschappelijk Onderzoek (Belgium), Flemish–Polish bilateral agreement BIL 01/31, and KBN research grant 2P03A 033 25 (Poland).     

Some 3/2-transitive permutation groups in which the stabilizer of two points is always Abelian

A monoidS is susceptible to having properties bearing upon all right acts overS such as: torsion freeness, flatness, projectiveness, freeness. The purpose of this note is to find necessary and sufficient conditions on a monoidS in order that, for example, all flat rightS-acts are free. We do this for all meaningful variants of such conditions and are able, in conjunction with the results of Skornjakov [8], Kilp [5] and Fountain [3], to describe the corresponding monoids, except in the case all torsion free acts are flat, where we have only some necessary condition. We mention in passing that homological classification of monoids has been discussed by several authors [3, 4, 5, 8].In the following,S will always stand for a monoid. A rightS-act is a setA on whichS acts unitarily from the right in the usual way, that is to saya(rs) = (ar)s, a1 =a (a A,r,s S) where 1 denotes the identity ofS.     

The Catenary and Tame Degree in Finitely Generated Commutative Cancellative Monoids

Problems involving chains of irreducible factorizations in atomic integral domains and monoids have been the focus of much recent literature. If S is a commutative cancellative atomic monoid, then the catenary degree of S (denoted c(S)) and the tame degree of S (denoted t(S)) are combinatorial invariants of S which describe the behavior of chains of factorizations. In this note, we describe methods to compute both c(S) and t(S) when M is a finitely generated commutative cancellative monoid.     

On Incidence Algebras of Combinatorial Inverse Monoids

We study the incidence algebra of the reduced standard division category of a combinatorial bisimple inverse monoid [with (E(S), ≤) locally finite], and we describe semigroups of poset type (i.e., a combinatorial inverse semigroup for which the corresponding Möbius category is a poset) as being combinatorial strict inverse semigroups. Up to isomorphism, the only Möbius-division categories are the reduced standard division categories of combinatorial inverse monoids.