明確な有限オートマトン

オートマトン理論において、一義的有限オートマトン( UFA ) は、各単語が最大で 1 つの受理経路を持つような非決定性有限オートマトン(NFA) です。各決定性有限オートマトン(DFA) は UFA ですが、その逆は成り立ちません。DFA、UFA、および NFA は、まったく同じクラスの形式言語を認識します。一方で、NFA は同等の DFA よりも指数的に小さくなる場合があります。他方、一部の問題は DFA では簡単に解けますが、UFA では簡単に解けません。たとえば、オートマトンAが与えられた場合、 Aの補集合を受け入れるオートマトンA ′ は、 Aが DFA であれば線形時間で計算できますが、UFA の場合は多項式時間で計算できないことが知られています。したがって、UFA は DFA の世界と NFA の世界が混ざり合ったものであり、場合によっては、DFA よりも小さなオートマトンと NFA よりも高速なアルゴリズムにつながります。

NFAは、5 要素の組 、 によって正式に表現されます。UFAは、各単語 に対して、次の条件を満たす状態 のシーケンス が最大で 1 つ存在するNFAです。${\displaystyle A=(Q,\Sigma ,\Delta ,q_{0},F)}$${\displaystyle w=a_{1}a_{2}...a_{n}}$${\displaystyle r_{0},r_{1},...,r_{n}}$${\displaystyle Q}$

1. ${\displaystyle r_{0}=q_{0}}$;
2. ${\displaystyle r_{i+1}\in \Delta (r_{i},a_{i+1})}$のために;${\displaystyle i=0,...n-1}$
3. ${\displaystyle r_{n}\in F}$。

言葉で言えば、これらの条件は、が によって受け入れられる場合、受け入れパス、つまり、 によってラベル付けされた初期状態から最終状態への 1 つのパスが存在することを述べています。 ${\displaystyle w}$${\displaystyle A}$${\displaystyle w}$

アルファベット{ a , b }上の単語の集合で、最後のn番目の文字がであるものとしましょう。図は、 n=2の場合にこの言語を受け入れるDFAとUFAを示しています。 ${\displaystyle L}$${\displaystyle a}$

を受け入れる最小の DFA には2 ^{n 個}の状態があり、{1... n } の各サブセットに 1 つずつあります。を受け入れる状態の UFA があります。これはn番目の最後の文字を推測し、文字のみが残っていることを確認します。 n番目の最後の文字は 1 つだけ存在するため、これは確かに明確です。${\displaystyle L}$${\displaystyle n+1}$${\displaystyle L}$${\displaystyle n-1}$

一般的な NFA の3 つのPSPACE困難な問題は DFA のPTIMEに属しており、現在検討中です。

UFA の言語が別の UFA の言語のサブセットであるかどうかは、多項式時間で決定可能です。

普遍性の問題^{[注 1]}と同値性の問題^{[注 2]}も包含問題への還元により PTIMEに属します。

状態と文字アルファベットを持つ非決定性有限オートマトンの場合、が明確であるかどうかは時間内に決定可能である。^[2]${\displaystyle A}$${\displaystyle n}$${\displaystyle m}$${\displaystyle O(n^{2}m)}$${\displaystyle A}$

• UFA Aと整数nが与えられた場合、 Aが受け入れるサイズnのワード数を多項式時間で数えることができます。これは、単純な動的プログラミング アルゴリズムで実行できます。Aとのすべての状態qについて、 qで始まり最終状態で終わる実行を持つサイズniのワード数を計算します。対照的に、同じ問題はNFA では#P 困難です。${\displaystyle i\in \{0,\ldots ,n\}}$
• 2つのUFAの直積（交差）はUFAである。^[3]
• 曖昧さのなさの概念は、有限状態トランスデューサと重み付きオートマトンにまで及びます。有限状態トランスデューサTが曖昧でない場合、各入力ワードはTによって最大で 1 つの出力ワードに関連付けられます。重み付きオートマトンAが曖昧でない場合、重みの集合は半環である必要はなく、代わりにモノイドを考慮するだけで十分です。実際、受け入れパスは最大で 1 つあります。

言語のあらゆるUFAには一定数の状態が必要であるという数学的証明は、シュミットによって開拓された。^[4]レオンは、 -状態のUFAと同等のDFAは最悪の場合でも状態を必要とすること、また有限曖昧^[注3]な-状態のNFAと同等のUFAは最悪の場合でも状態を必要とすることを証明した。^[5]${\displaystyle n}$${\displaystyle 2^{n}}$ ${\displaystyle n}$${\displaystyle 2^{n}-1}$

Jirásek、Jirásková、Šebej ^[6]は、UFA で表される言語上の基本的な正規演算の状態複雑性を研究しました。彼らは特に、であるすべての -状態の UFAに対して、それが受け入れる言語の補集合は最大で 状態を持つ UFA によって受け入れられることを証明しました。この結果は後に Indzhev と Kiefer ^[7]によって、すべての に対して最大で 状態であると改良されました。 ${\displaystyle n}$${\displaystyle n\geq 7}$${\displaystyle 2^{0.79n+\log n}}$${\displaystyle {\sqrt {n+1}}\cdot 2^{0.5n}}$${\displaystyle n\geq 0}$

ラスキン^[8]は、 UFAは多項式時間で補完できず、NFAにさえ補完できないことを示した。最悪の場合、n個の状態を持つUFAをNFAに補完するには、超多項式数の状態が必要であることを示した。この下限は後にGöös、Kiefer、Yuanによって改良された^[9]。

オホーチンは、1文字のアルファベットの場合、-状態のUFAと同等のDFAには最悪の場合でも状態が必要であることを証明した。^[10]${\displaystyle n}$${\displaystyle \exp \left(\Theta \left({\sqrt[{3}]{n(\ln n)^{2}}}\right)\right)}$

• Christof Löding, Unambiguous Finite Automata , Developments in Language Theory , (2013) pp. 29–30 (スライド)