言語等価ではなく、二重類似性に関してNFAを最小化するためのアルゴリズムはありますか?

DFAの最小化は、与えられたオートマトンを最小数の状態を持つ等価なものに変換する問題です。
等価は、言語等価であると解釈される。

ミルナーは二重類似性の概念を導入し、彼の書籍では、有限オートマトン(興味深いことに非決定論的なもの)の等価関係として最初にそれを研究することによって、バイミキシラリティを動機づけている。

それで、認識された言語の等価性の代わりに、この等価関係、二重類似性(初期状態のような)に関してNFAを最小化する問題についての研究は何ですか?

ベストアンサー

はい、ここを見てください:

Johanna Högberg, Andreas Maletti, Jonathan May, Backward and
forward bisimulation minimization of tree automata, Theoretical
Computer Science 410(37), 2009, pp. 3539-3552, https://doi.org/10.1016/j.tcs.2009.03.022

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です