Glossary for combinatorics on words: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 30: | Line 30: | ||
| abelian complexity || [[interval variety|variety]] of an [[interval class]] || | | abelian complexity || [[interval variety|variety]] of an [[interval class]] || | ||
|- | |- | ||
| Parikh vector || interval | | 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''|<sub>''a''</sub>. 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. | | (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. | ||
|} | |} | ||
== References == | == References == | ||
Revision as of 23:15, 4 November 2023
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 (Note: definitions may vary.) | 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. |
| spectrum[1] | interval class | |
| 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 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. |
References
- ↑ 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.