Namespaces
Variants
Actions

Difference between revisions of "Hall word"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (→‎References: + ZBL link)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
Hall words are obtained from Hall sets. A [[Word|word]] is as sequence of letters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h1100501.png" />, that is, elements chosen from a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h1100502.png" /> called an [[Alphabet|alphabet]]. A word is usually written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h1100503.png" />, or abbreviated by a single symbol: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h1100504.png" />. The length of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h1100505.png" /> is equal to the number of letters in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h1100506.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h1100507.png" />. One may concatenate words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h1100508.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h1100509.png" />, and this operation is concisely written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005010.png" />.
+
<!--
 +
h1100501.png
 +
$#A+1 = 44 n = 0
 +
$#C+1 = 44 : ~/encyclopedia/old_files/data/H110/H.1100050 Hall word
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
The elements of a [[Hall set|Hall set]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005011.png" /> can be viewed as completely bracketed words (or rooted planar binary trees with leaves labelled by generators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005012.png" />; cf. also [[Binary tree|Binary tree]]). These are defined recursively as brackets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005013.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005014.png" /> are bracketed words of lower weight; bracketed words of weight one correspond to the generators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005015.png" />. Moreover, a Hall set comes equipped with a total order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005016.png" /> (cf. also [[Order (on a set)|Order (on a set)]]).
+
{{TEX|auto}}
 +
{{TEX|done}}
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005017.png" /> be the Hall word obtained from a Hall element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005018.png" />. It is recursively defined as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005019.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005020.png" /> reduces to a letter, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005021.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005022.png" />. The total order on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005023.png" /> induces a total order on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005024.png" /> of Hall words. These words form a complete factorization; more precisely, any word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005025.png" /> is a non-increasing product of Hall words, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005026.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005027.png" />.
+
Hall words are obtained from Hall sets. A [[Word|word]] is as sequence of letters  $  ( a _ {1} \dots a _ {m} ) $,
 +
that is, elements chosen from a set  $  A $
 +
called an [[Alphabet|alphabet]]. A word is usually written as  $  a _ {1} \dots a _ {m} $,
 +
or abbreviated by a single symbol:  $  u = a _ {1} \dots a _ {m} $.
 +
The length of  $  u $
 +
is equal to the number of letters in  $  u $,
 +
i.e.  $  m $.
 +
One may concatenate words  $  u = a _ {1} \dots a _ {m} $,
 +
$  v = b _ {1} \dots b _ {n} $,
 +
and this operation is concisely written as  $  u v = a _ {1} \dots a _ {m} b _ {1} \dots b _ {n} $.
 +
 
 +
The elements of a [[Hall set|Hall set]]  $  H $
 +
can be viewed as completely bracketed words (or rooted planar binary trees with leaves labelled by generators  $  a _ {1} , a _ {2} , \dots $;
 +
cf. also [[Binary tree|Binary tree]]). These are defined recursively as brackets  $  t = [ t  ^  \prime  , t ^ {\prime \prime } ] $,
 +
where  $  t  ^  \prime  , t ^ {\prime \prime } $
 +
are bracketed words of lower weight; bracketed words of weight one correspond to the generators  $  a _ {1} , a _ {2} , \dots $.  
 +
Moreover, a Hall set comes equipped with a total order  $  \leq  _ {H} $(
 +
cf. also [[Order (on a set)|Order (on a set)]]).
 +
 
 +
Let  $  f ( t ) $
 +
be the Hall word obtained from a Hall element $  t $.  
 +
It is recursively defined as $  f ( t ) = a $
 +
if $  t = a \in A $
 +
reduces to a letter, and $  f ( t ) = f ( t  ^  \prime  ) f ( t ^ {\prime \prime } ) $
 +
if $  t = [ t  ^  \prime  , t ^ {\prime \prime } ] $.  
 +
The total order on $  H $
 +
induces a total order on the set $  \{ {f ( t ) } : {t \in H } \} $
 +
of Hall words. These words form a complete factorization; more precisely, any word $  w $
 +
is a non-increasing product of Hall words, $  w = f ( t _ {1} ) \dots f ( t _ {m} ) $
 +
with $  t _ {1} \geq  _ {H} \dots \geq  _ {H} t _ {m} $.
  
 
One particularly well-known example of complete factorization is the Lyndon factorization. The elements of this factorization are called Lyndon words (cf. [[Lyndon word|Lyndon word]]). Although Lyndon words are obtained from a particular Hall set, they may be directly defined as words lexicographically less than any of their non-empty proper right factors (cf. [[Lyndon word|Lyndon word]]). They possess many combinatorial properties. Almost all of these properties hold also for Hall words, with respect to an order now defined.
 
One particularly well-known example of complete factorization is the Lyndon factorization. The elements of this factorization are called Lyndon words (cf. [[Lyndon word|Lyndon word]]). Although Lyndon words are obtained from a particular Hall set, they may be directly defined as words lexicographically less than any of their non-empty proper right factors (cf. [[Lyndon word|Lyndon word]]). They possess many combinatorial properties. Almost all of these properties hold also for Hall words, with respect to an order now defined.
  
The order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005028.png" /> on the set of Hall words is extended to all words as follows. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005029.png" /> be words with Hall factorizations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005031.png" />. Then one defines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005032.png" /> if either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005034.png" /> or there exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005035.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005036.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005037.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005038.png" />. Incidentally, this order coincides with the lexicographic order when the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005039.png" /> is the Hall set from which one obtains Lyndon words.
+
The order $  \leq  _ {H} $
 +
on the set of Hall words is extended to all words as follows. Let $  w _ {1} , w _ {2} $
 +
be words with Hall factorizations $  w _ {1} = f ( t _ {1} ) \dots f ( t _ {m} ) $,  
 +
$  w _ {2} = f ( r _ {1} ) \dots f ( r _ {n} ) $.  
 +
Then one defines $  w _ {1} < _ {H} w _ {2} $
 +
if either $  m < n $
 +
and $  t _ {1} = r _ {1} \dots t _ {m} = r _ {m} $
 +
or there exists an $  i $
 +
such that $  1 \leq  i \leq  \min  ( m,n ) $
 +
with $  t _ {1} = r _ {1} \dots t _ {i - 1 }  = r _ {i - 1 }  $
 +
and $  t _ {i} < _ {H} r _ {i} $.  
 +
Incidentally, this order coincides with the lexicographic order when the set $  H $
 +
is the Hall set from which one obtains Lyndon words.
  
Hall words are words strictly less, with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005040.png" />, than any of their non-empty proper right factors. Equivalently, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005041.png" /> is a Hall word if it is strictly less, with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005042.png" />, than any of the circular shifts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005043.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110050/h11005044.png" />). For more details, see [[#References|[a1]]], [[#References|[a2]]].
+
Hall words are words strictly less, with respect to $  \leq  _ {H} $,  
 +
than any of their non-empty proper right factors. Equivalently, $  a _ {1} \dots a _ {m} $
 +
is a Hall word if it is strictly less, with respect to $  \leq  _ {H} $,  
 +
than any of the circular shifts $  a _ {i} \dots a _ {n} a _ {1} \dots a _ {i - 1 }  $(
 +
$  i = 2 \dots n $).  
 +
For more details, see [[#References|[a1]]], [[#References|[a2]]].
  
 
See also [[Lazard set|Lazard set]]; [[Hall polynomial|Hall polynomial]].
 
See also [[Lazard set|Lazard set]]; [[Hall polynomial|Hall polynomial]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  X. Viennot,  "Algèbres de Lie libres et monoïdes libres" , ''Lecture Notes in Mathematics'' , '''691''' , Springer  (1978)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  G. Melançon,  "Combinatorics of Hall trees and Hall words"  ''J. Combin. Th.'' , '''59A''' :  2  (1992)  pp. 285–308</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  X. Viennot,  "Algèbres de Lie libres et monoïdes libres" , ''Lecture Notes in Mathematics'' , '''691''' , Springer  (1978) {{ZBL|0395.17003}}</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  G. Melançon,  "Combinatorics of Hall trees and Hall words"  ''J. Combin. Th.'' , '''59A''' :  2  (1992)  pp. 285–308 {{ZBL|0761.05033}}</TD></TR>
 +
</table>

Latest revision as of 13:39, 20 March 2023


Hall words are obtained from Hall sets. A word is as sequence of letters $ ( a _ {1} \dots a _ {m} ) $, that is, elements chosen from a set $ A $ called an alphabet. A word is usually written as $ a _ {1} \dots a _ {m} $, or abbreviated by a single symbol: $ u = a _ {1} \dots a _ {m} $. The length of $ u $ is equal to the number of letters in $ u $, i.e. $ m $. One may concatenate words $ u = a _ {1} \dots a _ {m} $, $ v = b _ {1} \dots b _ {n} $, and this operation is concisely written as $ u v = a _ {1} \dots a _ {m} b _ {1} \dots b _ {n} $.

The elements of a Hall set $ H $ can be viewed as completely bracketed words (or rooted planar binary trees with leaves labelled by generators $ a _ {1} , a _ {2} , \dots $; cf. also Binary tree). These are defined recursively as brackets $ t = [ t ^ \prime , t ^ {\prime \prime } ] $, where $ t ^ \prime , t ^ {\prime \prime } $ are bracketed words of lower weight; bracketed words of weight one correspond to the generators $ a _ {1} , a _ {2} , \dots $. Moreover, a Hall set comes equipped with a total order $ \leq _ {H} $( cf. also Order (on a set)).

Let $ f ( t ) $ be the Hall word obtained from a Hall element $ t $. It is recursively defined as $ f ( t ) = a $ if $ t = a \in A $ reduces to a letter, and $ f ( t ) = f ( t ^ \prime ) f ( t ^ {\prime \prime } ) $ if $ t = [ t ^ \prime , t ^ {\prime \prime } ] $. The total order on $ H $ induces a total order on the set $ \{ {f ( t ) } : {t \in H } \} $ of Hall words. These words form a complete factorization; more precisely, any word $ w $ is a non-increasing product of Hall words, $ w = f ( t _ {1} ) \dots f ( t _ {m} ) $ with $ t _ {1} \geq _ {H} \dots \geq _ {H} t _ {m} $.

One particularly well-known example of complete factorization is the Lyndon factorization. The elements of this factorization are called Lyndon words (cf. Lyndon word). Although Lyndon words are obtained from a particular Hall set, they may be directly defined as words lexicographically less than any of their non-empty proper right factors (cf. Lyndon word). They possess many combinatorial properties. Almost all of these properties hold also for Hall words, with respect to an order now defined.

The order $ \leq _ {H} $ on the set of Hall words is extended to all words as follows. Let $ w _ {1} , w _ {2} $ be words with Hall factorizations $ w _ {1} = f ( t _ {1} ) \dots f ( t _ {m} ) $, $ w _ {2} = f ( r _ {1} ) \dots f ( r _ {n} ) $. Then one defines $ w _ {1} < _ {H} w _ {2} $ if either $ m < n $ and $ t _ {1} = r _ {1} \dots t _ {m} = r _ {m} $ or there exists an $ i $ such that $ 1 \leq i \leq \min ( m,n ) $ with $ t _ {1} = r _ {1} \dots t _ {i - 1 } = r _ {i - 1 } $ and $ t _ {i} < _ {H} r _ {i} $. Incidentally, this order coincides with the lexicographic order when the set $ H $ is the Hall set from which one obtains Lyndon words.

Hall words are words strictly less, with respect to $ \leq _ {H} $, than any of their non-empty proper right factors. Equivalently, $ a _ {1} \dots a _ {m} $ is a Hall word if it is strictly less, with respect to $ \leq _ {H} $, than any of the circular shifts $ a _ {i} \dots a _ {n} a _ {1} \dots a _ {i - 1 } $( $ i = 2 \dots n $). For more details, see [a1], [a2].

See also Lazard set; Hall polynomial.

References

[a1] X. Viennot, "Algèbres de Lie libres et monoïdes libres" , Lecture Notes in Mathematics , 691 , Springer (1978) Zbl 0395.17003
[a2] G. Melançon, "Combinatorics of Hall trees and Hall words" J. Combin. Th. , 59A : 2 (1992) pp. 285–308 Zbl 0761.05033
How to Cite This Entry:
Hall word. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Hall_word&oldid=15514
This article was adapted from an original article by G. Melançon (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article