推移閉包
transitive closure
$ Rの推移閉包とは、$ Rを含む最小の推移的関係$ R^+のこと
例
$ S=\{a,b,c\}があり、関係$ R=\{(a,b), (b,c)\}があるとする
この時、$ Rは推移的でない
なぜなら、$ aRb,bRcがあるのに、$ aRcがないから
ここで、それら加えた$ R^+ = \{(a,b),(b,c),(a,c)\}を考えた時、
これが$ Rの(最小の)推移閉包となる
https://ja.wikipedia.org/wiki/推移閉包
推移閉包を二階述語論理に加えると、クラスPSPACEが得られる。
そうなんだmrsekut.icon