An alternative presentation of the Schensted correspondence (Q1345529)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An alternative presentation of the Schensted correspondence |
scientific article |
Statements
An alternative presentation of the Schensted correspondence (English)
0 references
15 August 1995
0 references
In the author's opinion the paper presents a simple method for the evaluation of Schensted's symbols \(P\) and \(Q\) by applying functions \(\varphi(w)\) and \(\lambda(w)\), which are related to the decomposition of a string \(w\) given as a permutation into greatest increasing or decreasing substrings. However, if the traditional model of computation is applied then \(\varphi(w)\) and \(\lambda(w)\) can be obtained using exhaustive searching. Therefore, time \(O(| w|^ 2)\) is needed for the evaluation of the symbols \(Q\) and \(P\). In such a case the method is natural but not simple. Unfortunately it is very difficult to read the paper---mainly because of inconsistencies in the applied denotations and also because of the lack of sufficient explanations of the used symbols. The given examples are not supporting fully the given definitions and claims of the author. Especially it is difficult to read the proofs of the given propositions because of many shortcuts.
0 references
Schensted correspondence
0 references
Schensted symbols
0 references
permutation
0 references
model of computation
0 references