自己検証有限オートマトン

オートマトン理論において、自己検証有限オートマトン（SVFA ）は、 HromkovičとSchnitgerによって導入された対称的な種類の非決定性を備えた特別な種類の非決定性有限オートマトン（NFA）です。 ^[1] 一般に、自己検証非決定性では、各計算パスは、 yes、no、およびI do not knowの3つの可能な回答のいずれかで終了します。各入力文字列に対して、2つのパスが矛盾する回答を返すことはできません。つまり、同じ入力でyesとno の両方の回答を返すことはできません。少なくとも1つのパスがyesまたはnoの回答を返す必要があり、それがyesの場合、文字列は受け入れられたと見なされます。SVFAは、決定性有限オートマトン（DFA）およびNFAと同じクラスの言語を受け入れますが、状態の複雑さは異なります。

SVFA は、 6 要素タプルA =( Q、Σ、Δ、q ₀、F _a、F _r ) で形式的に表されます。ここで、 ( Q、Σ、Δ、q ₀、F _a ) はNFAであり、F _a、F _{r は}Qの互いに素な部分集合です。各単語w = a ₁ a ₂ … a _nについて、計算はQ内の状態r ₀、r ₁、…、r _nのシーケンスであり 、次の条件を満たします。

1. r ₀ = q ₀
2. r _i+1 ∈ Δ( r _i , a _i+1 )、ただしi = 0, …, n−1。

r _n ∈ F _aの場合、計算は受け入れ型であり、r _n ∈ F _{rの場合、計算は拒否型です。各}wに対して、少なくとも 1 つの受け入れ型計算または少なくとも 1 つの拒否型計算が存在する必要があります が、両方が存在する必要はありません。

各 DFA は SVFA ですが、その逆は成り立ちません。Jirásková とPighizzini ^[2]は、 n状態 のすべての SVFA に対して、同等の状態の DFA が存在することを証明しました。さらに、各正の整数nに対して、最小の同等の DFA が正確に 状態を持つようなn状態 SVFAが存在します。 ${\displaystyle g(n)=\Theta (3^{n/3})}$${\displaystyle g(n)}$

SVFAの状態複雑性に関する他の結果は、Jiráskováとその同僚によって得られました。^{[3] [4]}