Qシステム

Qシステムは、与えられた文法規則に従って有向グラフを変換する方法であり、 1967年から1970年にかけてモントリオール大学のアラン・コルメローによって自然言語処理で使用するために開発されました。モントリオール大学の機械翻訳システムであるTAUM-73は、言語形式としてQシステムを使用していました。

Q システムによって操作されるデータ構造は Q グラフです。これは、1 つのエントリ ノードと 1 つの出口ノードを持つ有向非巡回グラフで、各アークにはラベル付きの順序付きツリーがあります。入力文は通常、各アークに単語が含まれる線形 Q グラフで表されます (ツリーはこの単語でラベル付けされた 1 つのノードに縮小されます)。分析後、Q グラフは通常、1 つのアーク パスのバンドルであり、各アークには可能な分析ツリーが含まれます。生成後の目標は通常、必要な出力と同じ数のパスを生成することです。この場合も、アークごとに 1 つの単語が使用されます。

Q システムは、一連の Q 処理で構成されます。各処理は、<matched_pa​​th> == <added_pa​​th> [<condition>] という形式の一連の Q ルールです。Q 処理は、そのうちの 1 つが空の Q グラフを生成しない限り、順番に適用されます。空の Q グラフが生成された場合は、最後に取得された Q グラフが結果になります。ルールの 3 つの部分には、ラベル、ツリー、フォレストの変数を含めることができます。"==" の後のすべての変数は、<matched_pa​​th> 部分に出現する必要があります。変数はルールに対してローカルです。

Q 処理は、追加とクリーニングの 2 つのステップで機能します。最初に、インスタンス化(一方向の統合) を使用してすべてのルールを徹底的に適用し、現在の Q グラフに新しいパスを追加します (追加されたアークとそのツリーを使用して新しいパスを作成できます)。この追加プロセスが停止すると、ルールの適用に成功したすべてのアークが消去されるほか、エントリ ノードから終了ノードまでのどのパスにも存在しない未使用のアークもすべて消去されます。したがって、結果 (追加ステップが終了した場合) は、再び Q グラフになります。これにより、複数の Q システムを連鎖させ、それぞれが特殊なタスクを実行して、複雑なシステムを形成できます。たとえば、TAUM 73 は 15 の連鎖 Q システムで構成されていました。

Q-Systems の基本的な考え方の拡張、つまりインスタンス化を統一に置き換えること(簡単に言えば、ルールの右側部分に「新しい」変数を許可し、パラメーター化されたラベル付きツリーを論理項に置き換えること) により、 1972 年にAlain Colmerauerと Philippe Rousselによって設計されたPrologが生まれました。John Chandioux による逆方向の改良 (非決定性を削減し、型付きラベルを導入) により GramR が生まれ、 1985 年以降 METEOのプログラミングに使用されました。

2009年、GETALP ^[1] 、 Laboratoire d'Informatique de Grenoble ^{[2]のHong Thai Nguyenは、ANTLRを使用してQシステムとQグラフをコンパイルし、Christian Boitetが提案したアルゴリズム（以前の}Fortran実装 のソースは公開されておらず、失われていたため）を使用して、CでQ言語を再実装しました。その実装は、2010-11年にDavid Cattanéoによって修正、完成、拡張されました（歴史的バージョンのCDC6600の印刷可能な文字だけでなく、Unicode文字を使用したラベルにまで拡張されました）。

• METEOシステム

• Colmerauer, A: Les systèmes Q ou unformalisme pour Analyzer et synthétiser des sur ordinaryur.ミメオ、モントリオール、1969年。
• グエン、HT: TA 同種のシステムと TAO 異種のシステム。これらはUJF、グルノーブル、2009年。

• http://unldeco.imag.fr/unldeco/SystemsQ.po?localhost=/home/nguyenht/SYS-Q/MONITEUR/] 新しい Q-systems のデモ