Glossary for combinatorics on words: Difference between revisions

(35 intermediate revisions by 3 users not shown)

Line 1:

This page collects definitions and xen community equivalents of standard academic terminology used in {{w|combinatorics on words}}.

This page collects definitions and xen community equivalents of standard academic terminology used in {{w|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.)

Also check the main [[Glossary]].

{| class="wikitable sortable"

~~|+ Definitions~~

|-

! Academic term(s) !! Xen term(s) !! ~~Definition~~

! Academic term(s) !! Xen term(s) !! Brief definition

|-

| alphabet || steps || A countable set of symbols called letters.

|-

| ~~word~~ || ~~scale~~ || ~~A finite or infinite string of letters taken from an alphabet.~~

| size/cardinality of alphabet || [[arity]] ||

|-

| ~~conjugate~~ || ~~equivalent under modal rotation~~ ||

| [[word]] || scale || A finite, right-infinite, or bi-infinite string of letters taken from an alphabet.

|-

| circular word || [[periodic scale]] || An equivalence class of words that are conjugate~~, or equivalently, an infinite periodic word~~.

| 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''].

Line 24:

Line 27:

| primitive || single-period || ''w'' is ''primitive'' if for all ''u'' and all ''m'' ≥ 2, ''u''''m'' ≠ ''w''. A circular word is primitive if one (thus any) representative word of it is primitive.

|-

| ~~Christoffel word~~ || ~~brightest mode of a periodic [[MOS scale]]~~ ||

| 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''.

|-

| ~~Lyndon~~ word || ~~lexicographically brightest mode~~ || A word ~~that is lexicographically first among its rotations~~.

| Sturmian word || aperiodic MOS scale || An infinite binary word which has exactly (''n'' + 1) distinct length-''n'' subwords for every n ≥ 1.

|-

| ~~Sturmian~~ word ~~(Note: Definitions may vary.)~~ || ~~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.<ref name="paquin">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.</ref>

|-

| 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.<ref name="paquin"/>

|-

| [[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 ''c''''i'' is an intersection of the line with the coordinate plane ''x''''i'' = ''m''''i''.

Line 34:

Line 41:

| spectrum<ref>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.</ref> || [[interval class]] (generic interval) ||

|-

| abelian complexity || [[interval variety|variety]] of an [[interval class]] ||

| abelian complexity || (of the set of ''k''-steps) [[interval variety|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 number of occurrences of ''a'' in ''w''. The Parikh vector of a length-''k'' subword is a ''k''-step.

| 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''~~, the number of occurrences of any letter in~~ any two ''k''-steps differ by at most 1.

| (1-)[[balance]]d 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 ==

[[Category:Terms| ]]

[[Category:Scale]]

[[Category:Combinatorics on words]]

@@ Line 1: / Line 1: @@
-This page collects definitions and xen community equivalents of standard academic terminology used in {{w|combinatorics on words}}.
+This page collects definitions and xen community equivalents of standard academic terminology used in {{w|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.)
+Also check the main [[Glossary]].
 {| class="wikitable sortable"
-|+ Definitions
 |-
-! Academic term(s) !! Xen term(s) !! Definition
+! Academic term(s) !! Xen term(s) !! Brief definition
 |-
 | alphabet || steps || A countable set of symbols called letters.
 |-
-| word || scale || A finite or infinite string of letters taken from an alphabet.
+| size/cardinality of alphabet || [[arity]] ||
 |-
-| conjugate || equivalent under modal rotation ||
+| [[word]] || scale || A finite, right-infinite, or bi-infinite string of letters taken from an alphabet.
 |-
-| circular word || [[periodic scale]] || An equivalence class of words that are conjugate, or equivalently, an infinite periodic word.
+| 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''].
@@ Line 24: / Line 27: @@
 | primitive || single-period || ''w'' is ''primitive'' if for all ''u'' and all ''m'' &ge; 2, ''u''<sup>''m''</sup> &ne; ''w''. A circular word is primitive if one (thus any) representative word of it is primitive.
 |-
-| Christoffel word || brightest mode of a periodic [[MOS scale]] ||
+| 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''.
 |-
-| Lyndon word || lexicographically brightest mode || A word that is lexicographically first among its rotations.
+| Sturmian word || aperiodic MOS scale || An infinite binary word which has exactly (''n'' + 1) distinct length-''n'' subwords for every n &ge; 1.
 |-
-| Sturmian word (Note: Definitions may vary.) || aperiodic MOS scale || An infinite binary word which has exactly (''n'' + 1) distinct length-''n'' subwords for every n &ge; 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.<ref name="paquin">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.</ref>
+|-
+| 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.<ref name="paquin"/>
+|-
+| [[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 ''c''<sub>''i''</sub> is an intersection of the line with the coordinate plane ''x''<sub>''i''</sub> = ''m''<sub>''i''</sub>.
@@ Line 34: / Line 41: @@
 | spectrum<ref>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.</ref> || [[interval class]] (generic interval) ||
 |-
-| abelian complexity || [[interval variety|variety]] of an [[interval class]] ||
+| abelian complexity || (of the set of ''k''-steps) [[interval variety|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 &#124;''w''&#124;<sub>''a''</sub>, the number of occurrences of ''a'' in ''w''. The Parikh vector of a length-''k'' subword is a ''k''-step.
+| 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 &#124;''w''&#124;<sub>''a''</sub>, 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'', the number of occurrences of any letter in any two ''k''-steps differ by at most 1.
+| (1-)[[balance]]d 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 ==
+[[Category:Terms| ]]
+[[Category:Scale]]
+[[Category:Combinatorics on words]]