Knuth Relation

定义 Definition

Knuth relation（克努斯关系）：组合数学与代数组合中用于定义Knuth 等价（Knuth equivalence）的一组改写规则，常用于刻画plactic monoid（晶格/柏拉克单子）以及与Young 表（杨表）、RSK 对应相关的“词（word）”的等价类。直观上，它允许在满足特定大小关系条件时交换相邻字母的某些排列，而不改变对应的插入杨表。

（在字母/数字满足大小比较的字母表上，常见的两类 Knuth 关系可写为）

• 若 \(x \le y < z\)，则 \(xzy \equiv zxy\)
• 若 \(x < y \le z\)，则 \(yxz \equiv yzx\)

发音 Pronunciation (IPA)

/knuːθ rɪˈleɪʃən/

例句 Examples

Knuth relations let us rewrite a word without changing its insertion tableau.
Knuth 关系允许我们改写一个“词”，而不改变它对应的插入杨表。

Using Knuth relations, two different strings can be shown to be equivalent in the plactic monoid.
借助 Knuth 关系，可以证明两个不同的字符串在 plactic 单子中是等价的。

词源 Etymology

Knuth 来自计算机科学家与数学家 Donald E. Knuth（唐纳德·克努斯）的姓氏；relation 意为“关系/等价关系中的规则”。该术语用于指代他在相关研究中系统化的等价改写规则，后来成为代数组合与词的组合理论中的基础概念之一。

相关词 Related Words

• Knuth Equivalence
• Plactic Monoid
• Young Tableau
• RSK Correspondence
• Semistandard
• Word
• Rewrite Rule
• Permutation

文学与著作 Literary Works

• The Art of Computer Programming（Donald E. Knuth）：在更广泛的计算与数学背景中与“Knuth”相关思想频繁出现（尽管“Knuth relation”更常见于代数组合语境）。
• Algebraic Combinatorics on Words（M. Lothaire）：讨论词的等价、改写与相关代数结构时常涉及 Knuth 关系/Knuth 等价。
• Enumerative Combinatorics, Volume 2（Richard P. Stanley）：在与杨表、RSK、plactic 结构相关内容中常会提到 Knuth 等价与其生成关系。