TOPICS
Search

Subword


A subword of a word a_1a_2...a_n, in the sense used for the Bruhat order, is a word a_(i_1)a_(i_2)...a_(i_k) obtained by deleting zero or more letters without changing the order of the remaining letters. Thus 1<=i_1<i_2<...<i_k<=n; deleting all letters gives the empty word (Björner and Brenti 2005, p. 33).

For example, ac is a subword of abc, although its letters are not consecutive. This use of subword means a subsequence of the letters. Other contexts use the term for a substring, so the convention must be specified.

For a Coxeter group, the Bruhat order satisfies u<=v iff a reduced word for u is a subword of a reduced word for v (Björner and Brenti 2005, p. 34).


See also

Bruhat Order, Reduced Word, Subsequence, Substring, Word

Explore with Wolfram|Alpha

References

Björner, A. and Brenti, F. Combinatorics of Coxeter Groups. New York: Springer-Verlag, 2005.

Cite this as:

Weisstein, Eric W. "Subword." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Subword.html

Subject classifications