# Glossary for combinatorics on words

(Redirected from Primitive)

This page collects definitions and xen community equivalents of standard academic terminology used in combinatorics on words; it is primarily meant as a guide for searching for relevant academic literature in the field and is no substitute for reading sources carefully on a case-by-case basis, as various authors may use slightly deviating definitions.

(Scales are understood to be abstract with equaves unspecified.)

Academic term(s) Xen term(s) Brief definition
alphabet steps A countable set of symbols called letters.
size/cardinality of alphabet arity
word scale A finite, right-infinite, or bi-infinite string of letters taken from an alphabet.
conjugate equivalent under modal rotation Words u and v are conjugate if there exist words s and t such that u = st and v = ts. Compare: any two group elements of the form st and ts are also conjugate.
circular word, necklace periodic scale An equivalence class of words that are conjugate.
factor, subword u is a factor of w if w = yuv for words y and v. u is a factor of a circular word [w] if it is a factor of some representative of [w].
prefix u is a prefix of w if w = uv for some word v.
suffix u is a suffix of w if w = yu for some word y.
primitive single-period w is primitive if for all u and all m ≥ 2, umw. A circular word is primitive if one (thus any) representative word of it is primitive.
right (left) special factor A factor u of w is right (left) special in s if there exist distinct letters x, y such that both ux and uy (resp. xu and yu) are factors of s.
Sturmian word aperiodic MOS scale An infinite binary word which has exactly (n + 1) distinct length-n subwords for every n ≥ 1.
Christoffel word brightest mode of a periodic single-period MOS scale If p and q are relatively prime positive integers, then the Christoffel word of slope p/q is a word w of length p + q defined by w[i] = x if ip mod n > (i − 1)p mod n, y otherwise.[1]
episturmian word An infinite word s is episturmian provided that the set of the factors of s is closed under reversal and s has at most one right (equivalently left) special factor of each length.[1]
Lyndon word lexicographically brightest mode A word that is lexicographically first among its rotations, assuming an ordering on the letters.
cutting word, cutting sequence billiard scale The word of letters given by traversing a line of a given direction, where each letter ci is an intersection of the line with the coordinate plane xi = mi.
spectrum[2] interval class (generic interval)
abelian complexity (of the set of k-steps) variety of an interval class
Parikh vector; abelianization interval occurring in a scale; step decomposition A given subword w is associated with a Parikh vector whose coefficient for each letter a is |w|a, the number of occurrences of a in w. The Parikh vector of a length-k subword is a k-step in xen terminology.
(1-)balanced word (for binary words) MOS scale A word such that for any k and any two k-steps, the numbers of occurrences of any letter differ by at most 1.

## References

1. Geneviève Paquin, On a generalization of Christoffel words: epichristoffel words, Theoretical Computer Science, Volume 410, Issues 38–40, 2009, Pages 3782-3791, ISSN 0304-3975.
2. Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.