An alternative presentation of the Schensted correspondence
type: Item
instance of: scholarly article
title: An alternative presentation of the Schensted correspondence
zbMATH Open document ID: 0819.05063
DOI: 10.1016/0195-6698(95)90090-X
published in: European Journal of Combinatorics
publication date: 1995-08-15T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05E99
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 731896
zbMATH Keywords: Schensted correspondence
zbMATH Keywords: Schensted symbols
zbMATH Keywords: permutation
zbMATH Keywords: model of computation
author: Paul Moszkowski
reviewed by: Adam Kapralski
MaRDI profile type: Publication
cites work: Q5585020
cites work: Permutations, matrices, and generalized Young tableaux
cites work: Q3329580
cites work: Longest Increasing and Decreasing Subsequences
cites work: Quelques remarques sur une Construction de Schensted.
Recommended article: An occurrence of the Robinson-Schensted correspondence
Recommended article: Alternative proof of the Lyndon-Schützenberger theorem
Recommended article: Q4537316
Recommended article: Q2951995
Recommended article: An alternative proof of Diestel's theorem
Recommended article: Q3416917
Recommended article: A new theorem of the alternative
Recommended article: Q4179127
Recommended article: On the Leray-Schauder alternative
Recommended article: Q4323148
description: scientific article; zbMATH DE number 731896