Glossary for combinatorics on words

From Xenharmonic Wiki
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, umw. 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. 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.
  2. 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.