Hall word

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)
[a2]	G. Melançon, "Combinatorics of Hall trees and Hall words" J. Combin. Th. , 59A : 2 (1992) pp. 285–308