×

Semi-commutativity sets of morphisms over finitely generated free monoids. (English) Zbl 0814.94018

Summary: The notion of a semi-commutativity set for word mappings was defined by the second and the third author [ibid. 35(83), 255-270 (1991)] as an abstraction of a problem in cryptography. The notion is of special interest in case the mappings are morphisms. Then rather surprising constructions become possible. We investigate such constructions, paying special attention to exceptional values of inverse mappings. Some of our results bear a close relation to certain important issues in the theory of formal languages.

MSC:

94A60 Cryptography
20M15 Mappings of semigroups
68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
PDFBibTeX XMLCite