Alladi Ramakrishnan Hall

Continuous Time Words and their Plactic Monoid

Amritanshu Prasad

IMSc

The algorithm of C. Shensted, for the determination of the maximal length of a non-decreasing subword of a given word easily generalizes to continuous time words, where each letter of the alphabet is allowed to appear for a specified amount of time, rather than discretely. When one decides to identify words which gave the same output in Schensted's algorithm, Schuetzenberger's plactic monoid is obtained. This equivalence is generated by two relations due to Knuth.

We define a continuous time analogue of the plactic monoid, and also an analogue of the Knuth relations. Using this, we prove from first principles, the continuous time analogue of Green's theorem which characterizes the shape of the tableau obtained by Schensted's algorithm.