Hall word

Hall words are obtained from Hall sets. A word is as sequence of letters , that is, elements chosen from a set called an alphabet. A word is usually written as , or abbreviated by a single symbol: . The length of is equal to the number of letters in , i.e. . One may concatenate words , , and this operation is concisely written as .

The elements of a Hall set can be viewed as completely bracketed words (or rooted planar binary trees with leaves labelled by generators ; cf. also Binary tree). These are defined recursively as brackets , where are bracketed words of lower weight; bracketed words of weight one correspond to the generators . Moreover, a Hall set comes equipped with a total order (cf. also Order (on a set)).

Let be the Hall word obtained from a Hall element . It is recursively defined as if reduces to a letter, and if . The total order on induces a total order on the set of Hall words. These words form a complete factorization; more precisely, any word is a non-increasing product of Hall words, with .

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 on the set of Hall words is extended to all words as follows. Let be words with Hall factorizations , . Then one defines if either and or there exists an such that with and . Incidentally, this order coincides with the lexicographic order when the set is the Hall set from which one obtains Lyndon words.

Hall words are words strictly less, with respect to , than any of their non-empty proper right factors. Equivalently, is a Hall word if it is strictly less, with respect to , than any of the circular shifts (). 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