Primitive sets of words

DOI10.1016/J.TCS.2021.03.003MaRDI QIDQ2662680zbMATH OpenOpenAlexFDO

Authors Gabriele Fici, Antonio Restivo, G. Castiglione

Publication date 14 April 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.10668

zbMATH Keywords

\(k\)-maximal monoid bi-root hidden repetition primitive set pseudo-repetition

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: 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 s u b s e t e q 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 s u b s e t e q 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 s u b s e t e q 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 | < s q r t | w |

. That is, the bi-root of a word is unique provided the word is sufficiently long with respect to the size (sum of lengths) of the root. Our results are also compared to previous approaches that investigate pseudo-repetitions, where a morphic involutive function

h e t a

is defined on

A^{*}

. In this setting, the notions of

h e t a

-power,

h e t a

-primitive and

h e t a

-root are defined, and it is shown that any word has a unique

h e t a

-primitive root. This result can be obtained with our approach by showing that a word

w

is

h e t a

-primitive if and only if

w, h e t a (w)

is a primitive set.

Review text

The paper introduces the notion of a \emph{primitive set}, which is a set \(X\) such that the monoid \(M\) generated by \(X\) is not a proper submonoid of a monoid generated by at most \(|X|\) words. The monoid \(M\) is then called \(k\)-maximal with \(k = |X|\). The property of a set being primitive is stronger than the known property of being elementary. The paper shows that the intersection of two \(2\)-maximal submonoids is either empty or generated by a single primitive word. This in particular implies that a set \(X\) of rank two has a unique primitive root, that is, a primitive set \(Y\) such that \(X\) is contained in the monoid generated by \(Y\). The same does not hold for higher ranks. The paper also introduces the notion of a \emph{bi-root} of a word \(w\), which is a primitive set \(\{x,y\}\) such that \(w\) is in the monoid generated by \(\{x,y\}\). It is shown that there is at most one bi-root satisfying \(|x| + |y| < \sqrt{|w|}\). The results are also applied to pseudo-repetitions introduced in [\textit{E. Czeizler} et al., Theor. Comput. Sci. 411, No. 3, 617--630 (2010; Zbl 1184.68311)].

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Primitive sets of words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2662680)