2018/10/04 by Castiglione, Giuseppa, Fici, Gabriele, Restivo, Antonio
#68Q45 #68R15 #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.1810.02182
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^*. A submonoid M generated by k elements of A^* is k-maximal if there does not exist another submonoid generated by at most k words containing M. We call a set X ⊆ A^* primitive if it is the basis of a |X|-maximal submonoid. This extends the notion of primitive word: indeed, \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^*. The set Y is therefore called a primitive root of X. As a main result, we prove that if a set has rank 2, then it has a unique primitive root. This result cannot be extended to sets of rank larger than 2. For a single word w, we say that the set \x,y\ is a \em binary 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 binary root \x,y\ such that |x|+|y|