吃音の同等性

理論計算機科学において、吃音等価性^[1]は次のように記述される 関係である。

${\displaystyle \pi \sim _{st}\pi '}$、

パスとブロックを分割したものと見なすことができ、一方のパスのブロック内の状態は、もう一方のパスのブロック内の状態と同じように( ) とラベル付けされます。対応するブロックの長さは異なる場合があります。 ${\displaystyle \pi}$${\displaystyle \pi '}$${\displaystyle k^{\mathrm {th} }}$${\displaystyle L(\cdot )}$${\displaystyle k^{\mathrm {th} }}$

正式には、すべてのブロックに対して が成り立つような2 つの無限整数シーケンスとがある場合、これは 2 つの無限パスと がスタッターリング等価 ( ) であることとして表現できます。 ${\displaystyle \pi =s_{0},s_{1},\ldots }$${\displaystyle \pi '=r_{0},r_{1},\ldots }$${\displaystyle \pi \sim _{st}\pi '}$${\displaystyle 0=i_{0}、i_{1}、i_{2}、$${\displaystyle 0=j_{0}、j_{1}、j_{2}、j_{3}、j_{4}、j_{5}、j_{6}、j_{7}、j_{8}、j_{9}、j_{10}、j_{11}、j_{12}、j_{13}、j_{14}、j_{15}、j_{16}、j_{17}、j_{1$${\displaystyle k\geq 0}$${\displaystyle L(s_{i_{k}})=L(s_{i_{k}+1})=\ldots =L(s_{i_{k+1}-1})=L(r_{j_{k}})=L(r_{j_{k}+1})=\ldots =L(r_{j_{k+1}-1})}$

スタッタリング同値はバイシミュレーションと同じではありません。バイシミュレーションでは、線形時間/計算ツリーロジック（分岐時間ロジック）（様相論理）にある「最終的に」（または「最終的に」）演算子の意味を捉えることができないからです。いわゆる分岐バイシミュレーションを使用する必要があります。^[要出典]