# zbMATH — the first resource for mathematics

Topologies for the free monoid. (English) Zbl 0739.20032
Let $$L$$ be a recognizable subset of a free semigroup $$A^*$$, $$M$$ the syntactic monoid of $$L$$, $$E(M)$$ is the set of idempotents of $$M$$ and $$P$$ is the image of $$L$$ in $$M$$. It is conjectured that if for each $$s$$, $$t\in M$$ and each $$e\in E(M)$$, $$set\in P$$ implies $$st\in P$$, then $$L$$ is closed in $$\mathcal T$$, where the topology $$\mathcal T$$ on $$A^*$$ is defined by all the monoid morphisms from $$A^*$$ into a discrete finite group. The conjecture is proven in two particular cases: if $$P$$ is a submonoid of $$M$$, or if the idempotents of $$M$$ commute. The conjecture has several interesting consequences, for instance if it holds, then $$K(M)=D(M)$$ ( Rhodes’ Conjecture). Here $$K(M)=\cap 1\tau^{-1}$$, where the intersection is taken over all relational morphisms $$\tau$$ from $$M$$ into a group and $$D(M)$$ is the smallest submonoid of $$M$$ satisfying the condition: for every $$s$$, $$t\in M$$ such that either $$sts=s$$ or $$tst=t$$, from $$u\in D(M)$$ follows $$sut\in D(M)$$.
Reviewer: J.Henno (Naasa)

##### MSC:
 20M35 Semigroups in automata theory, linguistics, etc. 20M05 Free semigroups, generators and relations, word problems 20M15 Mappings of semigroups
Full Text:
##### References:
  Berstel, J, Transductions and context-free languages, (1979), Teubner Stuttgart · Zbl 0424.68040  Berstel, J; Crochemore, M; Pin, J.E, Thue-Morse sequence and p-adic topology for the free monoid, Discrete math., 76, 89-94, (1989) · Zbl 0675.05002  Bourbaki, N, Topologie générale, (1960), Hermann Paris · Zbl 0102.27104  Eilenberg, S; Eilenberg, S, ()  Hall, M, A topology for free groups and related groups, Ann. of math., 52, 127-139, (1950) · Zbl 0045.31204  Koch, H, Über beschränkte gruppen, J. algebra, 3, 206-224, (1966) · Zbl 0244.20025  Lallement, G, Semigroups and combinatorial applications, (1979), Wiley New York · Zbl 0421.20025  Lothaire, M, ()  Maroglis, S.W; Pin, J.E, Varieties of finite monoids and topology for the free monoid, (), 113-130  Ochsenschläger, P, Binomialkoeffizenten und shuffle-zahlen, (1981), Technischer Bericht, Fachbereich Informatik T.H. Darmstadt  Pin, J.E, Finite group topology and p-adic topology for free monoids, (), 445-455 · Zbl 0576.20044  Pin, J.E, Varieties of formal languages, (1986), North Oxford Academic London/Plenum, New York · Zbl 0632.68069  Pin, J.E, On the languages accepted by finite reversible automata, (), 237-249 · Zbl 0627.68069  Pin, J.E, A topological approach to a conjecture of rhodes, Bull. austral. math. soc., 38, 421-431, (1988) · Zbl 0659.20056  Reutenauer, Ch, Une topologie du monoïde libre, (), 33-49 · Zbl 0444.68076  Reutenauer, Ch, Sur mon article “une topologie du monoïde libre,”, (), 93-95 · Zbl 0461.68090  \scD. Scott, Infinite words, unpublished.  Straubing, H, Families of recognizable sets corresponding to certain varieties of finite monoids, J.pure appl. algebra, 15, 305-318, (1979) · Zbl 0414.20056  Straubing, H, A generalization of the schützenberger product of finite monoids, Theoret. comput. sci., 13, 137-150, (1981) · Zbl 0456.20048  Thérien, D, Sur LES monoïdes dont LES groupes sont résolubles, (), 89-101 · Zbl 0509.20053  Tilson, B, (), Chaps. XI and XII  \scP. Weil, Products of languages with counter, Theor. Comp. Sci., to appear. · Zbl 0704.68071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.