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 | A binary cutting word where the line has irrational slope. |
| cutting word, cutting sequence | billiard scale | The word of letters given by traversing a line of a given direction, where each letter c_i is an intersection of the line 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. |