Glossary for combinatorics on words - Revision history

Inthar at 04:29, 3 January 2026

2026-01-03T04:29:44Z

← Older revision		Revision as of 04:29, 3 January 2026
Line 11:		Line 11:
	\| alphabet \|\| steps \|\| A countable set of symbols called letters.		\| alphabet \|\| steps \|\| A countable set of symbols called letters.
	\|-		\|-
	\| size/cardinality of alphabet \|\| [[arity]] \|\|		\| size/cardinality of alphabet \|\| [[step variety]], [[arity]] \|\|
	\|-		\|-
	\| [[word]] \|\| scale \|\| A finite, right-infinite, or bi-infinite string of letters taken from an alphabet.		\| [[word]] \|\| scale \|\| A finite, right-infinite, or bi-infinite string of letters taken from an alphabet.

BudjarnLambeth at 03:25, 20 July 2025

2025-07-20T03:25:26Z

← Older revision		Revision as of 03:25, 20 July 2025
Line 2:		Line 2:

	(Scales are understood to be abstract with equaves unspecified.)		(Scales are understood to be abstract with equaves unspecified.)

			Also check the main [[Glossary]].

	{\| class="wikitable sortable"		{\| class="wikitable sortable"

Fredg999: Sort key

2025-04-18T03:20:38Z

Sort key

← Older revision		Revision as of 03:20, 18 April 2025
Line 47:		Line 47:

	== References ==		== References ==
	[[Category:Terms]]		[[Category:Terms\| ]]
	[[Category:Scale]]		[[Category:Scale]]
	[[Category:Combinatorics on words]]		[[Category:Combinatorics on words]]

BudjarnLambeth: Add link to orphaned page

2024-12-04T07:47:29Z

Add link to orphaned page

← Older revision		Revision as of 07:47, 4 December 2024
Line 33:		Line 33:
	\| 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"/>		\| 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.		\| [[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>.		\| 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>.

Inthar at 04:00, 19 February 2024

2024-02-19T04:00:01Z

← Older revision		Revision as of 04:00, 19 February 2024
Line 41:		Line 41:
	\| abelian complexity \|\| (of the set of ''k''-steps) [[interval variety\|variety]] of an [[interval class]]\|\|		\| abelian complexity \|\| (of the set of ''k''-steps) [[interval variety\|variety]] of an [[interval class]]\|\|
	\|-		\|-
	\| Parikh vector; abelianization \|\| 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 number of occurrences of ''a'' in ''w''. The Parikh vector of a length-''k'' subword is a ''k''-step in xen terminology.		\| 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''\|<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-)[[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.		\| (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.

Inthar at 22:55, 19 January 2024

2024-01-19T22:55:40Z

← Older revision		Revision as of 22:55, 19 January 2024
Line 5:		Line 5:
	{\| class="wikitable sortable"		{\| class="wikitable sortable"
	\|-		\|-
	! Academic term(s) !! Xen term(s) !! Brief ~~efinition~~		! Academic term(s) !! Xen term(s) !! Brief definition
	\|-		\|-
	\| alphabet \|\| steps \|\| A countable set of symbols called letters.		\| alphabet \|\| steps \|\| A countable set of symbols called letters.

Inthar at 22:55, 19 January 2024

2024-01-19T22:55:28Z

← Older revision		Revision as of 22:55, 19 January 2024
Line 4:		Line 4:

	{\| class="wikitable sortable"		{\| class="wikitable sortable"
	~~\|+ Definitions~~
	\|-		\|-
	! Academic term(s) !! Xen term(s) !! ~~Definition~~		! Academic term(s) !! Xen term(s) !! Brief efinition
	\|-		\|-
	\| alphabet \|\| steps \|\| A countable set of symbols called letters.		\| alphabet \|\| steps \|\| A countable set of symbols called letters.

Inthar: The latter definition fails to distinguish primitive circular words from nonprimitive ones.

2024-01-19T22:54:12Z

The latter definition fails to distinguish primitive circular words from nonprimitive ones.

← Older revision		Revision as of 22:54, 19 January 2024
Line 16:		Line 16:
	\| 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.		\| 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~~, or equivalently, an infinite periodic word~~.		\| 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''].		\| 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''].

Inthar at 23:48, 27 December 2023

2023-12-27T23:48:20Z

← Older revision		Revision as of 23:48, 27 December 2023
Line 30:		Line 30:
	\| Sturmian word \|\| aperiodic MOS scale \|\| An infinite binary word which has exactly (''n'' + 1) distinct length-''n'' subwords for every n ≥ 1.		\| 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 [[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>		\| 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"/>		\| 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"/>

Inthar at 16:54, 26 December 2023

2023-12-26T16:54:42Z

← Older revision		Revision as of 16:54, 26 December 2023
Line 10:		Line 10:
	\| alphabet \|\| steps \|\| A countable set of symbols called letters.		\| alphabet \|\| steps \|\| A countable set of symbols called letters.
	\|-		\|-
	\| size/cardinality of alphabet \|\| arity \|\|		\| size/cardinality of alphabet \|\| [[arity]] \|\|
	\|-		\|-
	\| [[word]] \|\| scale \|\| A finite, right-infinite, or bi-infinite string of letters taken from an alphabet.		\| [[word]] \|\| scale \|\| A finite, right-infinite, or bi-infinite string of letters taken from an alphabet.