×

zbMATH — the first resource for mathematics

On the generation of words using the composition operation. (Russian) Zbl 1054.68106
In 1962, A. I. Shirshov introduced the composition operation [Sib. Math. Zh. 3, 132–137 (1962; Zbl 0143.25602)] whose particular case is the concatenation operation. Previously Yu. V. Merekin developed the suffix method for obtaining lower bounds on the complexity of generated words for the concatenation operation. In the paper under review he extends this method to the composition operation.

MSC:
68R15 Combinatorics on words
68Q45 Formal languages and automata
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDF BibTeX XML Cite