Reflexive Transitive Closure

Definition 定义

reflexive transitive closure（自反传递闭包）：在关系 \(R\)（或有向图的边关系）基础上，加入必要的边使其同时满足：

自反（reflexive）：对任意元素 \(a\)，都有 \(aRa\)（允许“原地可达”）。
传递（transitive）：若 \(aRb\) 且 \(bRc\)，则 \(aRc\)。

直观理解：表示“从 \(a\) 出发经过零步或多步沿关系 \(R\) 能到达 \(b\)”的可达关系，常记作 \(R^\*\)（而仅传递闭包常记作 \(R^+\)，对应“至少一步”）。

Pronunciation 发音

/riˈflɛksɪv ˈtrænzɪtɪv ˈkloʊʒər/

Examples 例句

The reflexive transitive closure of the “follows” relation tells us who can be reached by following zero or more steps.
“关注/跟随”关系的自反传递闭包告诉我们：通过零步或多步跟随，哪些人是可达的。

In graph theory and databases, we often compute the reflexive transitive closure to answer reachability queries efficiently, even when the original relation is not transitive.
在图论和数据库中，我们常计算自反传递闭包来高效回答“可达性”查询，即使原始关系本身并不具备传递性。

Etymology 词源

这是由三个英语词组成的技术短语：

reflexive 源自拉丁语 reflectere（“折回、反向”），在数学里引申为“指向自身”，即 \(aRa\)。
transitive 来自拉丁语 transire（“穿过、越过”），对应“可通过中间步骤传递”。
closure 源自拉丁语 claudere（“关闭、封闭”），在数学中表示“补齐到某种性质为止”的最小扩充（最小闭包）。

Related Words 相关词

Literary Works 文学作品

Aho & Ullman 等《Compilers: Principles, Techniques, and Tools》（编译原理“龙书”）——在形式语言/自动机与可达性相关讨论中常涉及闭包概念与 \(R^\*\) 记号。
Cormen, Leiserson, Rivest, Stein《Introduction to Algorithms》——在图算法与可达性、传递闭包（如 Warshall/Floyd-Warshall 思想相关）中出现。
Hopcroft, Motwani, Ullman《Introduction to Automata Theory, Languages, and Computation》——在正则表达式的 Kleene 星（对应“零次或多次”）与关系 \(R^\*\) 的语义联系中常被提及。
Ebbinghaus & Flum《Finite Model Theory》——在一阶逻辑扩展（如可达性/传递闭包逻辑）相关章节中使用“(reflexive) transitive closure”术语。