Glossary for combinatorics on words

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, um ≠ w. 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.
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.
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	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.