In this and following sections, words are considered to be elements of some ordered monoid, that is a free monoid whose generators have an explicit ordering. The most important example is the monoid of words generated by the positive integers, though Magma also allows the creation of finitely generated ordered monoids. The words in this section are developed in connection with the theory of Young tableaux (see section Tableaux), which are defined over some ordered set of labels (generators of an ordered monoid in Magma).
The importance of the ordering on the generators is in the definition of
an equivalence
known as Knuth equivalence.
Knuth equivalence is defined by the two relations
yzx ∼ yxz x < y ≤ z
xzy ∼ zxy x ≤ y < z
The plactic monoid is the quotient of an ordered monoid with respect to Knuth equivalence. This plactic monoid is in fact isomorphic to the monoid of tableaux over the same generators. Elements of the plactic monoid are represented by a canonical representative from the Knuth equivalence class of the ordered monoid. This canonical representative is in fact the row word of the corresponding tableau (see section Tableaux).
An ordered monoid is a free monoid with an ordered basis. Magma has two different types of ordered monoids. The first is the monoid of words over the positive integers, which retain their natural ordering. The second are finitely generated monoids, whose generators may be assigned names.
Given a positive integer n, return the monoid with n ordered generators.
Return the ordered monoid of words over the positive integers.
Given an ordered monoid O, return its identity element. i.e., the null word.
Given an ordered monoid O and a positive integer i, return the ith generator of O.
Given an ordered monoid O, and a sequence of elements from O, return the word w1 ... wn.
Given the ordered monoid O over the positive integers, and a sequence of integers, return the word i1 ... in.
Given two words w1 and w2 from the same ordered monoid, return true if they are equal.
Given two words w1 and w2 from the same ordered monoid, return their product under word concatenation.
Two words w1 and w2 from the same monoid are Knuth equivalent if they can be transformed into one another using elementary Knuth transformations, (defined in the introduction to this section).
Given a word w from an ordered monoid, expressed as a product of generators, return the ith generator in the product.
Given a word w from the ordered monoid of positive integers, return w as a sequence of integers.
Given a word w from an ordered monoid, return its length.
Given a word w from an ordered monoid, return a sequence of non-negative integers denoting its content. The content of a word is a sequence where the ith position denotes the number of occurrences of the ith generator in the word.
A word w from an ordered monoid is said to be a reverse lattice word (or Yamanouchi word) if for any n>0, the last n letters of w have a content which is a partition.
Given a word w from an ordered monoid, return a weakly increasing subsubsequence of w of maximal length. This sequence is not necessarily unique.
Given a word w from an ordered monoid and some positive integer k, return a sequence of k distinct increasing subsequences of the word w, such that the maximal number of entries from w is used. Empty sequences are returned if all entries from w are used. These sequences are not necessarily unique.
> O := OrderedIntegerMonoid(); > O; The monoid of words over the positive integers > > w1 := O ! [3,5,2,8]; > w1; 3 5 2 8 > w2 := O ! [6,7,2,4]; > w2; 6 7 2 4 > > w2[3]; 2 > Eltseq(w1); [ 3, 5, 2, 8 ] > > w1*w2; 3 5 2 8 6 7 2 4
> O<a,b,c,d> := OrderedMonoid(4); > O; The monoid of words over 4 generators: a b c d > > w := a*b*a*d*c; > w; a b a d c
> O := OrderedIntegerMonoid(); > w := O ! [1,3,4,2,3,4,1,2,2,3,3,2]; > > MaximalIncreasingSequence(w); 1 1 2 2 2 3 > MaximalIncreasingSequences(w,2); [ 1 1 2 2 2 3 , 2 3 3 ] > MaximalIncreasingSequences(w,3); [ 1 1 2 2 2 3 , 2 3 3 , 3 4 4 ] > MaximalIncreasingSequences(w,4); [ 1 1 2 2 2 3 , 2 3 3 , 3 4 4 , Id(O) ]
The plactic monoid of an ordered monoid is the quotient defined by Knuth equivalence. Elements of a plactic monoid are equivalence classes of words from the original ordered monoid, and are represented by a canonical representative.
Given an ordered monoid O, return the plactic monoid obtained by factoring O by Knuth equivalence.
Return the plactic monoid obtained by factoring the ordered monoid over the positive integers by Knuth equivalence.
Given a plactic monoid P, return the ordered monoid on which P is based.
Given a plactic monoid P, return its identity element which is the null word.
Given a plactic monoid P and a positive integer i, return the ith generator of P.
Given a plactic monoid P, and a sequence of elements from P, return the product u1 ... un.
Given the plactic monoid P over the positive integers, and a sequence of integers, return the element of P corresponding to the Knuth equivalence class of i1 ... in.
Given a plactic monoid P, and a word w from the ordered monoid that its based on, return the element of P corresponding to the Knuth equivalence class of w.
Given a plactic monoid P, and a sequence of elements from the ordered monoid that its based on, return the element of P corresponding to the Knuth equivalence class of w1 ... wn.
Given a plactic monoid P and a tableau t which are both associated with the same ordered monoid, return the element of P which is uniquely associated to t.
Given two elements u1 and u2 from the same plactic monoid, return true if they are equal.
Given two elements u1 and u2 belonging to the same plactic monoid, return their product which is inherited from word concatenation in the ordered monoid.
Given a element u from a plactic monoid, return its length. The length of a word is invariant under Knuth equivalence and so is well defined for elements of the plactic monoid.
Given a word u from a plactic monoid, return a sequence of non-negative integers denoting its content. The content of a word is a sequence where the ith position denotes the number of occurrences of the ith generator in the word. The content of a word is invariant under Knuth equivalence and so is well defined for elements of the plactic monoid.
> O := OrderedIntegerMonoid(); > P := PlacticIntegerMonoid(); > > w1 := O ! [2,7,4,8,1,5,9]; > w1; 2 7 4 8 1 5 9 > P!w1; 7 2 8 1 4 5 9First we look at a word that is Knuth equivalent to w1,
> w2 := O ! [7,2,1,8,4,5,9]; > w2; 7 2 1 8 4 5 9 > > IsKnuthEquivalent(w1,w2); true > (P!w1) eq (P!w2); trueand then one that is not Knuth equivalent.
> w3 := O ! [7,1,5,8,2,9,4]; > w3; > 7 1 5 8 2 9 4 > IsKnuthEquivalent(w1,w3); false > (P!w1) eq (P!w3); false > P!w3; 7 5 8 1 2 4 9
> O<a,b,c,d,e> := OrderedMonoid(5); > P := PlacticMonoid(O); > P; The plactic monoid of words over 5 generators: a b c d e > > w := b*c*e*e*a*d*a*d; > w; b c e e a d a d > Length(w); 8 > Content(w); [ 2, 1, 1, 2, 2 ] > > u := P!w; > u; a a b c d d e e > Length(u); 8 > Content(u); [ 2, 1, 1, 2, 2 ]