Glossary for combinatorics on words
Jump to navigation
Jump to search
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.[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.0 1.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.
- ↑ 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.