Glossary for combinatorics on words

This page collects definitions and xen community equivalents of standard academic terminology used in combinatorics on words.

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

Definitions

Academic term(s)	Xen term(s)	Definition
alphabet	steps	A countable set of symbols called letters.
word	scale	A finite or infinite string of letters taken from an alphabet.
conjugate	equivalent under modal rotation
circular word	periodic scale	An equivalence class of words that are conjugate, or equivalently, an infinite periodic word.
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.
Christoffel word	brightest mode of a periodic MOS scale
Lyndon word	lexicographically brightest mode	A word that is lexicographically first among its rotations.
Sturmian word (Note: Definitions may vary.)	aperiodic MOS scale	An infinite binary word which has exactly (n + 1) distinct length-n subwords for every n ≥ 1.
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	variety of an interval class
Parikh vector	interval occurring in a scale	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.
(1-)balanced word	(for binary words) MOS scale	A word such that for any k, the number of occurrences of any letter in any two k-steps differ by at most 1.