×

zbMATH — the first resource for mathematics

On the groups of codes with empty kernel. (English) Zbl 1202.20071
A word \(v\in A^*\) is an internal factor of a word \(x\in A^*\) iff \(x=uvw\) for some nonempty words \(u,w\). The kernel of a set \(X\subset A^*\) is the set of words from \(X\) which are internal factors of some word from \(X\). It is shown, that if \(X\) is a code with empty kernel, \(F\) the set of internal factors of words from \(X\) and \(\varphi\) the syntactic morphism of the submonoid \(X^*\), then any group \(G\) contained in \(\varphi(A^*\setminus F)\) is cyclic. A subclass of codes with empty kernel are semaphore codes, thus this is a generalization of a result of M. P. Schützenberger [Inf. Control 7, 23-26 (1964; Zbl 0122.15004)].

MSC:
20M35 Semigroups in automata theory, linguistics, etc.
20M05 Free semigroups, generators and relations, word problems
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata. Cambridge University Press, Cambridge (2009) · Zbl 1187.94001
[2] Eilenberg, S.: Automata, Languages, and Machines, vol. B. Academic Press, New York, 1976 [Harcourt Brace Jovanovich Publishers], With two chapters (”Depth decomposition theorem” and ”Complexity of semigroups and morphisms”) by Bret Tilson, Pure and Applied Mathematics, vol. 59
[3] Froidure, V., Pin, J.-E.: Algorithms for computing finite semigroups. In: Foundations of Computational Mathematics, Rio de Janeiro, 1997, pp. 112–126. Springer, Berlin (1997) · Zbl 0876.20034
[4] Lallement, G.: Semigroups and Combinatorial Applications. Wiley, New York (1979). Pure and Applied Mathematics, a Wiley-Interscience publication · Zbl 0421.20025
[5] Schützenberger, M.-P.: On the synchronizing properties of certain prefix codes. Inf. Control 7, 23–36 (1964) · Zbl 0122.15004 · doi:10.1016/S0019-9958(64)90232-3
[6] Sch”utzenberger, M.-P.: Sur les monoides finis dont les groupes sont commutatifs. Rev. Fr. Autom. Inf. Rech. Opér. Sér. Rouge 8(R-1), 55–61 (1974) · Zbl 0294.20056
[7] Wielandt, H.: Finite Permutation Groups. Academic Press, New York (1964) · Zbl 0138.02501
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.