×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berstel, J, Transductions and context-free languages, (1979), Teubner Stuttgart · Zbl 0424.68040
[2] 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
[3] Bourbaki, N, Topologie générale, (1960), Hermann Paris · Zbl 0102.27104
[4] Eilenberg, S; Eilenberg, S, ()
[5] Hall, M, A topology for free groups and related groups, Ann. of math., 52, 127-139, (1950) · Zbl 0045.31204
[6] Koch, H, Über beschränkte gruppen, J. algebra, 3, 206-224, (1966) · Zbl 0244.20025
[7] Lallement, G, Semigroups and combinatorial applications, (1979), Wiley New York · Zbl 0421.20025
[8] Lothaire, M, ()
[9] Maroglis, S.W; Pin, J.E, Varieties of finite monoids and topology for the free monoid, (), 113-130
[10] Ochsenschläger, P, Binomialkoeffizenten und shuffle-zahlen, (1981), Technischer Bericht, Fachbereich Informatik T.H. Darmstadt
[11] Pin, J.E, Finite group topology and p-adic topology for free monoids, (), 445-455 · Zbl 0576.20044
[12] Pin, J.E, Varieties of formal languages, (1986), North Oxford Academic London/Plenum, New York · Zbl 0632.68069
[13] Pin, J.E, On the languages accepted by finite reversible automata, (), 237-249 · Zbl 0627.68069
[14] Pin, J.E, A topological approach to a conjecture of rhodes, Bull. austral. math. soc., 38, 421-431, (1988) · Zbl 0659.20056
[15] Reutenauer, Ch, Une topologie du monoïde libre, (), 33-49 · Zbl 0444.68076
[16] Reutenauer, Ch, Sur mon article “une topologie du monoïde libre,”, (), 93-95 · Zbl 0461.68090
[17] \scD. Scott, Infinite words, unpublished.
[18] Straubing, H, Families of recognizable sets corresponding to certain varieties of finite monoids, J.pure appl. algebra, 15, 305-318, (1979) · Zbl 0414.20056
[19] Straubing, H, A generalization of the schützenberger product of finite monoids, Theoret. comput. sci., 13, 137-150, (1981) · Zbl 0456.20048
[20] Thérien, D, Sur LES monoïdes dont LES groupes sont résolubles, (), 89-101 · Zbl 0509.20053
[21] Tilson, B, (), Chaps. XI and XII
[22] \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.