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.)
| 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. | |
| 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 | aperiodic MOS scale | |
| cutting word, cutting sequence | billiard scale | The word of letters where each letter being an intersection with the coordinate plane x_i = m_i. |
| abelian complexity | variety of an interval class | |
| Parikh vector | interval; the Parikh vector of a length-k subword is a k-step. | A given subword w is associated with a Parikh vector whose coefficient for each letter a is |w|a. |
| (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. |