形式等価判定
リタイム回路の等価判定: 論理回路をレジスタの一方から他方へ移す必要が生じることがあり、これが判定問題を複雑化させる。
逐次等価判定: 組み合わせレベルでは全く異なる2つのマシンが、同じ入力に対して同じ出力を返す場合がある。この場合、組み合わせ問題に縮減させることはできず、より汎用的な手法を必要とする。
ソフトウェアプログラムの等価性: つまり、N入力でM出力の正しく定義されたプログラムの等価判定である。概念的にはソフトウェアを状態機械に変換することができる(コンパイラと実際のコンピュータが行っているのは、プログラムの状態機械への変換である)。そして理論的には各種特性を判定することで同じ出力を生成するかどうかを確認できる。これは出力生成タイミングが異なる可能性もあるため、逐次等価判定よりも難しい。しかし、判定は可能であり、研究が進められている。