|
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.
O ! 1 : MonOrd, RngInt -> MonOrdElt
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.
Eltseq(w) : MonOrdElt -> SeqEnum
Given a word w from the ordered monoid of positive integers,
return w as a sequence of integers.
# w : MonOrdElt -> RngIntElt
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.
We create the ordered monoid over the positive integers and look at a few
elements.
> 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
We create a finitely generated ordered monoid and create an element.
> 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
We take a word of integers and look at
weakly increasing subsequences of maximal length.
> 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.
P ! 1 : MonPlc, RngIntElt -> MonPlcElt
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.
# u : MonPlcElt -> RngIntElt
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.
We create both the ordered monoid and plactic monoid over the integers and
look at several elements.
> 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 9
First we look at a word that is Knuth equivalent to w 1,
> 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);
true
and 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
We create a finitely generated ordered monoid, its associated plactic monoid,
and look at some properties which are invariant under Knuth equivalence.
> 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 ]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|