フィルタリングされたポップアウト再帰遷移ネットワーク

フィルタ付きポッピング再帰遷移ネットワーク( FPRTN ) ^{[ 1 ]} 、または単にフィルタ付きポッピングネットワーク( FPN ) は、サブルーチンジャンプからの復帰にアクセプタ状態とリターン状態が同じキーにマッピングされる必要がある状態からキーへのマップで拡張された再帰遷移ネットワーク( RTN ) ^{[ 2 ]}です。RTNは、リターン状態のスタックで拡張された有限状態オートマトンと見なすことができる有限状態マシンです。また、遷移と${\displaystyle \varepsilon }$-遷移、RTNは呼び出し遷移を定義できます。これらの遷移は、遷移のターゲット状態をスタックにプッシュし、マシンを呼び出し先の状態にすることで、サブルーチンジャンプを実行します。アクセプタ状態に到達するたびに、スタックが空でない限り、スタックの最上位にある戻り状態がポップアウトされ、マシンはこの状態になります。

本稿では、フィルタリングされたポップ再帰遷移ネットワークをFPNと略記するが、この略語は曖昧な表現である（例：ファジーペトリネット）。フィルタリングされたポップネットワークとFPRTNは、曖昧さのない代替表現である。

FPNは構造です${\displaystyle (Q,K,\Sigma ,\delta ,\kappa ,Q_{I},F)}$どこ

• ${\displaystyle Q}$は有限の状態の集合であり、
• ${\displaystyle K}$は有限個のキーの集合です。
• ${\displaystyle \Sigma }$は有限の入力アルファベットです。
• ${\displaystyle \delta :Q\times (\Sigma \cup \{\varepsilon \}\cup Q)\to Q}$は部分遷移関数であり、${\displaystyle \varepsilon }$空の記号であるため、
• ${\displaystyle \kappa :Q\to K}$状態とキーのマップです。
• ${\displaystyle Q_{I}\subseteq Q}$は初期状態の集合であり、
• ${\displaystyle F\subseteq Q}$これは受理状態の集合です。

遷移は、FPNをソース状態から別の状態へ移行させる可能性を表します。$qs$目標状態へ$qt$追加のアクションを実行することによって。このアクションに応じて、明示的に定義された以下のタイプの遷移を区別します。

• ${\displaystyle \varepsilon }$-遷移は次の形式の遷移です$\displaystyle \delta (q_{s},\varepsilon )\to q_{t}}$追加のアクションは行わず、
• 消費遷移は、次の形式の遷移です。$\displaystyle \delta (q_{s},\sigma )\to q_{t}}$入力シンボルを消費する${\displaystyle \sigma }$、 そして
• 呼び出し遷移は次の形式の遷移です。$\displaystyle \delta (q_{s},q_{c})\to q_{t}}$そしてサブルーチンを実行して、呼び出された状態にジャンプする$qc$到着する前に$qt$。

呼び出し遷移の動作は、暗黙的に定義された 2 種類の遷移によって制御されます。

• 各呼び出しの遷移について$\displaystyle \delta (q_{s},q_{c})\to q_{t}}$FPNは暗黙的にプッシュ遷移を定義し、マシンを$qs$に$qc$押すことによって$qt$スタックに、そして
• 各状態のペアについて${\displaystyle (q_{f},q_{r})\in F\times Q}$FPNは暗黙のうちに、マシンを$q_f$に$q_r$ポップすることで$q_r$スタックから$q_r$スタックの最上位の状態であり、${\displaystyle \kappa (q_{f})=\kappa (q_{r})}$。

プッシュ遷移はサブルーチンジャンプを初期化し、ポップ遷移はreturn文と同等です。

（自然言語）テキストは、出力付きRTNを適用することでメタ情報で強化できます。たとえば、XMLタグを挿入するRTNは、プレーンテキストを構造化されたXMLドキュメントに変換するために使用できます。自然言語文法を表す出力付きRTNは、各テキスト文の構文構造を区切り、追加します（構文解析を参照）。出力付きRTNは、関連情報を含むテキストセグメントを単にマークすることができます（情報抽出を参照）。曖昧な文法を表す出力付きRTNを適用すると、入力の可能な翻訳または解釈のセットが得られます。このセットを計算すると、出力付きRTN用のEarleyパーサーであっても、最悪の場合のコストは指数関数的になります^{[ 3 ]。}これは、翻訳の数が入力の長さに対して指数関数的に増加するケースがあるためです。たとえば、自然言語の文の解釈の数は、未解決の前置詞句の付加の数に対して指数関数的に増加します。 ^{[ 4 ] [ 5 ]}

• 文「少女は望遠鏡で猿を見た」では、少女が望遠鏡を使ったのか、猿が望遠鏡を持っていたのかは不明である（2 ^{1 の}解釈）。
• 文「少女は庭で望遠鏡を使って猿を見た」では、猿が庭にいたのか、それとも庭でその行為が行われたのかは不明である（2 ^{2 の}解釈）。
• 文「少女は庭の木の下で望遠鏡で猿を見た」では、猿が木の下にいたのか、それとも行動が木の下で行われたのかは不明である（2 ^{3 の}解釈）。
• 等

FPN は、この変換セットのコンパクトな表現として機能し、Earley 型パーサーによって 3 乗時間で計算することを可能にします。^{[ 1 ]} FPN の状態は、出力のないRTNの Earley パーサーの実行状態 (命令ステップを参照) に対応し、FPN の遷移は入力シンボルの可能な変換に対応します。${\displaystyle \kappa }$結果として得られる FPN のマップは、表現された出力セグメントと認識された入力セグメントとの対応関係を示します。認識された入力シーケンスが与えられた場合$\displaystyle \sigma _{1}\ldots \sigma _{l}}$そしてFPNパス${\displaystyle p}$州からスタート${\displaystyle q}$そして、ある状態に至る$q'$、${\displaystyle p}$入力セグメントの可能な翻訳を表します$\displaystyle \sigma _{\kappa (q)+1}\ldots \sigma _{\kappa (q^{\prime })}}$フィルタリングされたポップ機能は、FPN パスが切断された入力セグメントや重複する入力セグメントの変換を表すことを避けるために必要です。FPN 呼び出しでは、呼び出し先の状態からアクセプタ状態への複数の変換パスが含まれる場合があります。これらのパスに対応する入力セグメントは同じ開始点を共有しますが、必ずしも同じ長さではありません。呼び出しを終了したアクセプタ状態と同じ入力点に対応する戻り状態のみが有効な戻り状態です。