ネストされた単語

コンピュータサイエンス、より具体的にはオートマトンと形式言語理論において、ネストされた単語は、線形順序構造をモデル化するために伝統的に使用されていた単語と、階層構造をモデル化するために伝統的に使用されていた順序付きランクなし木の共同一般化として、 AlurとMadhusudanによって提案された概念である。ネストされた単語の有限状態アクセプタ、いわゆるネストされた単語オートマトンにより、単語に対する有限オートマトンをより表現力豊かに一般化することができる。有限ネストされた単語オートマトンによって受け入れられる言語の線形エンコーディングは、可視プッシュダウン言語のクラスを与える。後者の言語クラスは、正規言語と決定論的文脈自由言語のちょうど中間に位置する。2004年に導入されて以来、これらの概念はその分野で多くの研究を引き起こしてきた。^[1]

正式な定義

入れ子の単語を定義するには、まず対応する関係を定義します。非負の整数 の場合、表記は集合 を表し、特別な場合は となります。 ${\displaystyle \ell}$ ${\displaystyle [\ell ]}$ ${\displaystyle \{1,2,\ldots ,\ell -1,\ell \}}$ ${\displaystyle [0]=\emptyset }$

長さの一致する関係↝は次のようなのサブセットです。 ${\displaystyle \ell \geq 0}$ ${\displaystyle \{-\infty ,1,2,\ldots ,\ell -1,\ell \}\times \{1,2,\ldots ,\ell -1,\ell ,\infty \}}$

1. すべてのネストエッジは順方向です。つまり、i  ↝  jの場合、 i  <  jです。
2. ネストされた辺は、決して共通の有限の位置を持たない。つまり、−∞ <  i  < ∞の場合、 h  ↝  iとなる位置hは最大で1つしか存在せず、 i ↝ jとなる位置j も最大で1つしか存在しない。そして
3. ネストされたエッジが交差することはありません。つまり、i  ↝  jかつi  ′ ↝  j  ′となるようなi  <  i  ′ ≤  j  <  j  ′は存在しません。

位置iは次のように呼ばれる。

• コールポジション、あるjに対してi↝jの場合、
• i ↝ ∞の場合、保留中の呼び出し
• 戻り位置、あるhに対してh ↝ iの場合、
• −∞ ↝ iの場合は保留中の戻り、および
• 残りのすべてのケースでは内部位置になります。

アルファベットΣ 上の長さのネストされた単語は、ペア ( w、↝) です。ここで、wは Σ 上の長さの単語または文字列であり、 ↝ は長さの一致する関係です。 ${\displaystyle \ell}$ ${\displaystyle \ell}$ ${\displaystyle \ell}$

ネストされた単語を通常の単語にエンコードする

アルファベット上のネストされた単語は、タグ付きアルファベット上の「通常の」単語にエンコードできます。ここで、Σ の各シンボルaには、3 つのタグ付き対応があります。シンボル⟨aは、 aのラベルが付けられたネストされた単語内の呼び出し位置をエンコードし、シンボルa⟩は、 aのラベルが付けられた戻り位置をエンコードし、シンボルa自体が、 aのラベルが付けられた内部位置を表します。より正確には、φ をΣ 上のネストされた単語を 上の単語にマッピングする関数とし、各ネストされた単語 ( 、↝) は単語 にマッピングされます。ここで、の場合、文字は⟨a、a、a⟩に等しく、iはそれぞれ (保留中の可能性のある) 呼び出し位置、内部位置、 (保留中の可能性のある) 戻り位置です。 ${\displaystyle \Sigma =\{a_{1},a_{2},\ldots ,a_{n}\}}$ ${\displaystyle {\hat {\シグマ }}}$ ${\displaystyle {\hat {\シグマ }}}$ ${\displaystyle w_{1}w_{2}\cdots w_{\ell }}$ ${\displaystyle x_{1}x_{2}...x_{\ell}}$ ${\displaystyle x_{i}}$ ${\displaystyle w_{i}=a}$

例

例えば、n = ( w ,↝)を、 w = abaabcccaで対応関係↝ = {(−∞,1),(2,∞),(3,4),(5,7),(8,∞) }を満たす3進アルファベット上のネストされた単語とします。この単語を単語としてエンコードすると、φ ( n ) = a ⟩⟨ b ⟨ aa ⟩⟨ bcc ⟩⟨ caとなります。

オートマタ

ネストされた単語オートマトン

ネストされた単語オートマトンには有限の数の状態があり、古典的な文字列上の決定論的有限オートマトンとほぼ同じように動作します。古典的な有限オートマトンでは、入力された単語を左から右に読み取り、j番目の文字を読み取った後のオートマトンの状態は、読み取る前のオートマトンの状態によって決まります。 ${\displaystyle w=w_{1}\cdots w_{\ell }}$ ${\displaystyle w_{j}}$ ${\displaystyle w_{j}}$

ネストされた単語オートマトンにおいて、ネストされた単語 (w,↝) 内の位置は戻り位置となる可能性があります。その場合、読み取り後の状態は、オートマトンが読み取り前に有していた線形状態だけでなく、対応する呼び出し位置にあった時点でオートマトンによって伝播された階層状態にも依存します。単語の正規言語と同様に、ネストされた単語の集合 L は、何らかの（有限状態の）ネストされた単語オートマトンによって受理される場合、 正規であると呼ばれます。${\displaystyle j}$ ${\displaystyle w_{j}}$ ${\displaystyle w_{j}}$

可視プッシュダウンオートマトン

ネストされた単語オートマトンとは、ネストされた単語を受け入れるオートマトンモデルです。（通常の）単語に対して動作する同等のオートマトンモデルも存在します。つまり、決定性プッシュダウンオートマトンの概念は、決定性プッシュダウンオートマトンの概念の制約です。

AlurとMadhusudan ^[2]によれば、決定性可視プッシュダウンオートマトンは 次の 6要素タプルとして正式に定義される。${\displaystyle M=(Q,{\hat {\Sigma }},\Gamma ,\delta ,q_{0},F)}$

• ${\displaystyle Q}$ は有限の状態集合であり、
• ${\displaystyle {\hat {\シグマ }}}$ は入力アルファベットであり、通常のプッシュダウンオートマトンとは異なり、3つの集合、、に分割される。アルファベットは呼び出し記号の集合を表し、戻り記号を含み、集合は内部記号を含む。${\displaystyle \Sigma _{\text{c}}}$ ${\displaystyle \Sigma _{\text{r}}}$ ${\displaystyle \Sigma _{\text{int}}}$ ${\displaystyle \Sigma _{\text{c}}}$ ${\displaystyle \Sigma _{\text{r}}}$ ${\displaystyle \Sigma _{\text{int}}}$
• ${\displaystyle \Gamma}$ はスタックアルファベットと呼ばれる有限集合であり、空のスタックを表す特別な記号を含み、${\displaystyle \bot \in \Gamma }$
• ${\displaystyle \delta =\delta _{\text{c}}\cup \delta _{\text{r}}\cup \delta _{\text{int}}}$ は遷移関数であり、呼び出し遷移、戻り遷移、内部遷移に対応する3つの部分に分割されます。
  • ${\displaystyle \delta_{\text{c}}\colonQ\times\Sigma_{\text{c}}\toQ\times\Gamma}$ 、通話遷移機能
  • ${\displaystyle \delta_{\text{r}}\colonQ\times\Sigma_{\text{r}}\times\Gamma\toQ}$ 、戻り遷移関数
  • ${\displaystyle \delta_{\text{int}}:Q\times \Sigma_{\text{int}}\to Q}$ 、内部遷移関数、
• ${\displaystyle q_{0}\in \,Q}$ は初期状態であり、
• ${\displaystyle F\subseteq Q}$ は受け入れ状態の集合です。

可視プッシュダウンオートマトンの計算の概念は、プッシュダウンオートマトンの計算の概念の制限です。可視プッシュダウンオートマトンは、呼び出しシンボルの読み取り時にスタックにシンボルを追加するのみで、戻りシンボルの読み取り時にはスタックの最上位要素を削除するのみで、内部イベントの読み取り時にはスタックを変更しません。受理状態で終了する計算は、受理計算です。 ${\displaystyle a_{\text{c}}\in \Sigma _{\text{c}}}$ ${\displaystyle a_{\text{r}}\in \Sigma _{\text{r}}}$ ${\displaystyle a_{\text{i}}\in \Sigma _{\text{int}}}$

その結果、可視プッシュダウンオートマトンは、同じ入力記号でスタックにプッシュしたりスタックからポップしたりすることができません。したがって、の任意の分割に対して、この言語は可視プッシュダウンオートマトンは受理できませんが、この言語を受理するプッシュダウンオートマトンは存在します。 ${\displaystyle L=\{a^{n}ba^{n}\mid n\in \mathrm {N} \}}$ ${\displaystyle \Sigma }$

タグ付きアルファベット上の言語 が決定論的可視プッシュダウンオートマトンによって受け入れられる場合、それは可視プッシュダウン言語と呼ばれます。 ${\displaystyle L}$ ${\displaystyle {\hat {\シグマ }}}$ ${\displaystyle L}$

非決定性可視プッシュダウンオートマトン

非決定性可視プッシュダウンオートマトンは、決定性オートマトンと同様に表現力に優れています。したがって、非決定性可視プッシュダウンオートマトンは決定性オートマトンに変換できますが、非決定性オートマトンに状態がある場合、決定性オートマトンは最大で状態を持つ可能性があります。^[3]${\displaystyle s}$ ${\displaystyle 2^{s^{2}}}$

意思決定の問題

オートマトン の記述の大きさを とすると、単語nがオートマトンによって時間 で受け入れられるかどうかを判定できます。特に、空虚問題は時間 で解けます。 が固定されている場合、これは時間と空間で決定可能です。ここで、はストリーミングシーイングにおけるnの深さです。これはまた、空間と時間で決定可能であり、深さ の一様ブール回路によっても決定可能です。^[2]${\displaystyle |A|}$ ${\displaystyle A}$ ${\displaystyle O(|A|^{3}\ell )}$ ${\displaystyle O(|A|^{3})}$ ${\displaystyle A}$ ${\displaystyle O(\ell )}$ ${\displaystyle O(d)}$ ${\displaystyle d}$ ${\displaystyle O(\log(\ell ))}$ ${\displaystyle O(\ell ^{2}\log(\ell ))}$ ${\displaystyle O(\log \ell )}$

2つの非決定性オートマトンAとBについて、 Aが受け入れる単語の集合がBが受け入れる単語のサブセットであるかどうかを判定することはEXPTIME完全である。また、受け入れない単語が存在するかどうかを判定することもEXPTIME完全である。^[2]

言語

可視プッシュダウンオートマトンの定義が示すように、決定性可視プッシュダウンオートマトン は決定性プッシュダウンオートマトンの特殊なケースと見なすことができます。したがって、上の可視プッシュダウン言語の集合VPL は、 の記号集合上の決定性文脈自由言語の集合DCFLのサブセットを形成します。特に、入れ子になった単語から一致関係を削除する関数は、入れ子になった単語上の通常の言語を文脈自由言語に変換します。 ${\displaystyle \,{\hat {\シグマ }}}$ ${\displaystyle \,{\hat {\シグマ }}}$

閉鎖特性

可視プッシュダウン言語の集合は、以下の操作に対して閉じている: ^{[3] [2]}

• 集合演算:
  • 連合
  • 交差点
  • 補体、

こうしてブール代数が生じます。

• クリーネスター
• 連結
• 逆転
• 文字列準同型

交差演算については、単純な積構成によって、与えられた2つのVPAとをシミュレートするVPA Mを構築できます(Alur & Madhusudan 2004)。 については、が と与えられていると仮定します。すると、オートマトンMについて、状態集合は、初期状態は、最終状態集合は、スタックアルファベットは、初期スタックシンボルは となります。 ${\displaystyle M_{1}}$ ${\displaystyle M_{2}}$ ${\displaystyle i=1,2}$ ${\displaystyle M_{i}}$ ${\displaystyle (Q_{i},\ {\hat {\Sigma }},\ \Gamma _{i},\ \delta _{i},\ s_{i},\ Z_{i},\ F_{i})}$ ${\displaystyle \,Q_{1}\times Q_{2}}$ ${\displaystyle \left(s_{1},s_{2}\right)}$ ${\displaystyle F_{1}\times F_{2}}$ ${\displaystyle \,\Gamma _{1}\times \Gamma _{2}}$ ${\displaystyle (Z_{1},Z_{2})}$

呼び出しシンボルの読み取り時に が状態 にある場合、 スタック シンボルをプッシュして 状態 に移行します。ここで、 は入力の読み取り 時に 状態から に​​遷移するときにによってプッシュされるスタック シンボルです。 ${\displaystyle M}$ ${\displaystyle (p_{1},p_{2})}$ ${\displaystyle \left\langle a\right.}$ ${\displaystyle M}$ ${\displaystyle (\gamma _{1},\gamma _{2})}$ ${\displaystyle (q_{1},q_{2})}$ ${\displaystyle \gamma_{i}}$ ${\displaystyle M_{i}}$ ${\displaystyle p_{i}}$ ${\displaystyle q_{i}}$ ${\displaystyle \left\langle a\right.}$

内部シンボルを読み取ったときに が状態 にある場合、を読み取ったとき に が状態 から に遷移するときは常に、 は状態 になります。 ${\displaystyle M}$ ${\displaystyle (p_{1},p_{2})}$ ${\displaystyle a}$ ${\displaystyle M}$ ${\displaystyle (q_{1},q_{2})}$ ${\displaystyle M_{i}}$ ${\displaystyle p_{i}}$ ${\displaystyle q_{i}}$

戻りシンボルの読み取り時に が状態 にある場合、 は シンボルをスタックからポップして状態 に移行します。ここで は、の読み取り 時に状態 からに遷移するときにによってポップされるスタック シンボルです。 ${\displaystyle M}$ ${\displaystyle (p_{1},p_{2})}$ ${\displaystyle \left.a\right\rangle }$ ${\displaystyle M}$ ${\displaystyle (\gamma _{1},\gamma _{2})}$ ${\displaystyle (q_{1},q_{2})}$ ${\displaystyle \gamma_{i}}$ ${\displaystyle M_{i}}$ ${\displaystyle p_{i}}$ ${\displaystyle q_{i}}$ ${\displaystyle \left.a\right\rangle }$

上記の構成の正しさは、シミュレートされたマシンとにおけるプッシュとポップの動作が、入力シンボルの読み取りに応じて同期しているという事実に大きく依存しています。実際、決定性プッシュダウンオートマトンでは、同様のシミュレーションはもはや不可能です。なぜなら、決定性文脈自由言語のより大きなクラスは、もは​​や交差に関して閉じていないからです。 ${\displaystyle M_{1}}$ ${\displaystyle M_{2}}$

上に示した連結の構成とは対照的に、可視プッシュダウンオートマトンに対する補完構成は、決定論的プッシュダウンオートマトンに対する標準的な構成^[4]と平行している。

さらに、文脈自由言語のクラスと同様に、可視プッシュダウン言語のクラスは接頭辞閉包と反転に対して閉じており、したがって接尾辞閉包も同様です。

他の言語クラスとの関係

Alur & Madhusudan (2004) は、可視プッシュダウン言語は McNaughton (1967) が示唆した括弧言語よりも汎用的であると指摘しています。Crespi Reghizzi & Mandrioli (2012) が示したように、可視プッシュダウン言語は、厳密には演算子先行文法によって記述される言語のクラスに含まれます。演算子先行文法は Floyd (1963) によって導入され、同じ閉包特性と特徴を備えています (ω 言語と論理およびオートマトン ベースの特徴付けについては、Lonati 他 (2015) を参照)。文脈自由文法の一般化である連言文法と比較して、Okhotin (2011)は、線形連言言語が可視プッシュダウン言語のスーパークラスを形成することを示しています。この記事の最後にある表は、可視プッシュダウン言語のファミリーをチョムスキー階層の他の言語ファミリーとの関係で示しています。 Rajeev AlurとParthasarathy Madhusudan ^{[5] [6]}は、正規二分木言語のサブクラスを可視プッシュダウン言語に関連付けました。 harvtxt error: no target: CITEREFOkhotin2011 (help)

他の記述モデル

目に見えるプッシュダウン文法

可視プッシュダウン言語は、まさに可視プッシュダウン文法で記述できる言語です。^[2]

可視プッシュダウン文法は、文脈自由文法の制約として定義できます。可視プッシュダウン文法Gは、以下の4つの要素で定義されます。

${\displaystyle G=(V=V^{0}\cup V^{1}\,,\Sigma \,,R\,,S\,)}$ どこ

• ${\displaystyle V^{0}\,}$ とは互いに素な有限集合であり、各要素は非終端文字または変数と呼ばれます。各変数は文中の異なる種類の句または節を表します。各変数は によって定義される言語のサブ言語を定義します。のサブ言語は、保留中の呼び出しや保留中の戻り値がないものです。${\displaystyle V^{1}\,}$ ${\displaystyle v\in V}$ ${\displaystyle G\,}$ ${\displaystyle V^{0}\,}$
• ${\displaystyle \Sigma \,}$ は、文の実際の内容を構成する、とは互いに素な終端記号の有限集合である。終端記号の集合は、文法 によって定義された言語のアルファベットである。${\displaystyle V\,}$ ${\displaystyle G\,}$
• ${\displaystyle R\,}$ はからへの有限関係であり、 となる。 の要素は、文法の（書き換え）規則または生成規則と呼ばれる。書き換え規則には3種類ある。 、およびについて、${\displaystyle V\,}$ ${\displaystyle (V\cup \Sigma )^{*}}$ ${\displaystyle \exists \,w\in (V\cup \Sigma )^{*}:(S,w)\in R}$ ${\displaystyle R\,}$ ${\displaystyle X,Y\in V,Z\in V^{0}}$ ${\displaystyle a\in {\hat {\Sigma }}}$ ${\displaystyle b\in {\hat {\Sigma }}}$
  • ${\displaystyle X\to \epsilon }$
  • ${\displaystyle X\to aY}$ そしてもしそうならそして${\displaystyle X\in V^{0}}$ ${\displaystyle Y\in V^{0}}$ ${\displaystyle a\in \Sigma }$
  • ${\displaystyle X\to \langle aZb\rangle Y}$ そしてもし${\displaystyle X\in V^{0}}$ ${\displaystyle Y\in V^{0}}$
• ${\displaystyle S\in V\,}$ は開始変数（または開始シンボル）であり、文全体（またはプログラム）を表すために使用されます。

ここで、アスタリスクはクリーネスター演算を表し、空の単語です。 ${\displaystyle \epsilon }$

均一ブール回路

長さの単語が与えられたネストされた単語オートマトンによって受け入れられるかどうかという問題は、深さの均一ブール回路によって解くことができる。^[2]${\displaystyle \ell }$ ${\displaystyle \mathrm {O} (\log \ell )}$

論理的な説明

入れ子になった単語上の正規言語は、 2つの単項述語callとreturn、線形後続、および一致関係↝を持つモナド 二階述語論理によって記述される言語の集合とまったく同じである。 ^[2]

参照

• モデル検査

注記

1. Google Scholarの「nested words」または「visibly pushdown」の検索結果
2. アルールとマドゥスダン (2009)
3. Alur & Madhusudan (2004)
4. ホップクロフト＆ウルマン（1979年、238ページ以降）。
5. Alur, R.; Madhusudan, P. (2004). 「Visibly pushdown languages」（PDF） . Proceedings of the third-sixth annual ACM symposium on Theory of compute - STOC '04. pp.  202– 211. doi :10.1145/1007352.1007390. ISBN 978-1581138528. S2CID  7473479。第4節、定理5、
6. Alur, R.; Madhusudan, P. (2009). 「単語へのネスト構造の追加」(PDF) . Journal of the ACM . 56 (3): 1– 43. CiteSeerX 10.1.1.145.9971 . doi :10.1145/1516512.1516518. S2CID  768006. 第7節

参考文献

• フロイド, RW (1963年7月). 「構文解析と演算子の優先順位」. Journal of the ACM . 10 (3): 316– 333. doi : 10.1145/321172.321179 . S2CID  19785090.
• マクノートン, R. (1967). 「括弧文法」. Journal of the ACM . 14 (3): 490–500 . doi : 10.1145/321406.321411 . S2CID  10926200.
• Alur, R.; Arenas, M.; Barcelo, P.; Etessami, K.; Immerman, N.; Libkin, L. (2008). Grädel, Erich (編). 「ネストされた単語のための一階述語論理と時相論理」.コンピュータサイエンスにおける論理的手法. 4 (4). arXiv : 0811.0537 . doi :10.2168/LMCS-4(4:11)2008. S2CID  220091601.
• クレスピ・レギッツィ、ステファノ、マンドリオリ、ディーノ (2012). 「演算子の優先順位と可視プッシュダウン特性」.コンピュータとシステム科学ジャーナル. 78 (6): 1837– 1867. doi : 10.1016/j.jcss.2011.12.006 .
• ロナティ、ヴィオレッタ。マンドリオーリ、ディノ。パネッラ、フェデリカ。プラデッラ、マッテオ (2015)。 「演算子優先順位言語: そのオートマトンの理論と論理の特徴付け」。SIAM ジャーナル オン コンピューティング。44 (4): 1026–1088。土井:10.1137/140978818。hdl : 2434/352809。
• Okhotin, Alexander: 線形接続言語と文脈自由言語のサブファミリーの比較、第 37 回コンピュータ サイエンスの理論と実践の最新動向に関する国際会議 (SOFSEM 2011)。
• ホップクロフト, ジョン・E.; ウルマン, ジェフリー・D. (1979). 『オートマトン理論、言語、計算入門』 . アディソン・ウェスレー. ISBN 978-0-201-02988-8。

外部リンク

• ネストされた単語と目に見えるプッシュダウン言語
• 可視プッシュダウンオートマトン – ネストされた単語上のオートマトン
• Complexity Zooのクラス VPL