2020/05/20 by Castiglione, Giuseppa, Fici, Gabriele, Restivo, Antonio
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2005.10668
Given a (finite or infinite) subset X of the free monoid A^* over a finite alphabet A, the rank of X is the minimal cardinality of a set F such that X ⊆ F^*. We say that a submonoid M generated by k elements of A^* is \em k-maximal if there does not exist another submonoid generated by at most k words containing M. We call a set X ⊆ A^* \em primitive if it is the basis of a |X|-maximal submonoid. This definition encompasses the notion of primitive word -- in fact, \w\ is a primitive set if and only if w is a primitive word. By definition, for any set X, there exists a primitive set Y such that X ⊆ Y^*. We therefore call Y a \em primitive root of X. As a main result, we prove that if a set has rank 2, then it has a unique primitive root. To obtain this result, we prove that the intersection of two 2-maximal submonoids is either the empty word or a submonoid generated by one single primitive word. For a single word w, we say that the set \x,y\ is a \em bi-root of w if w can be written as a concatenation of copies of x and y and \x,y\ is a primitive set. We prove that every primitive word w has at most one bi-root \x,y\ such that |x|+|y|