Loading article…
コンピュータ サイエンスでは、言語の表現力(表現力または表現度とも呼ばれる)とは、その言語で表現および伝達できるアイデアの幅のことです。言語の表現力が高ければ高いほど、表現に使用できるアイデアの種類と量が多くなります。
たとえば、ウェブオントロジー言語表現言語プロファイル (OWL2 EL) には、OWL2 RL (ルール言語) で表現できる概念 (否定など) がありません。そのため、OWL2 EL は OWL2 RL よりも表現力が劣ると言えます。これらの制限により、OWL2 EL では OWL2 RL よりも効率的な (多項式時間) 推論が可能になります。そのため、OWL2 EL は、より効率的な推論 (知識表現言語の処理) と引き換えに、表現力をいくらか犠牲にしています。[1]
情報の説明
表現力という言葉は、さまざまな意味で使われることがあります。それは、その言語で表現できるアイデアの尺度を意味することもあります。[2]
- 容易さ（理論的な表現力）に関係なく
- 簡潔かつ容易に（実用的な表現力）
最初の意味は、形式言語理論、数理論理学、プロセス代数など、言語とその意味の形式的な記述を扱う数学と論理学の分野で支配的です。[2]
非公式な議論では、この用語はしばしば2番目の意味、またはその両方を指します。これはプログラミング言語について議論する場合によく当てはまります。[3] [ページが必要] この用語の非公式な使用を公式化する努力がなされてきました。[4]
表現力の概念は常に、その言語が記述できる特定の種類のものに相対的なものであり、この用語は通常、同じ種類のもの、または少なくとも比較可能な種類のものを記述する言語を比較するときに使用されます。[4]
言語と形式主義の設計には、表現力と分析可能性の間のトレードオフが伴う。形式主義が表現できるものが増えるほど、形式主義のインスタンスが何を言っているのか理解するのが難しくなる。 決定問題は答えるのが難しくなるか、完全に決定不可能になる。[5]
例
形式言語理論では
形式言語理論では、主に文脈自由文法や正規表現などの文字列のセットを記述する形式主義を研究します。形式主義の各インスタンス、たとえば各文法や各正規表現は、特定の文字列のセットを記述します。この文脈では、形式主義の表現力はそのインスタンスが記述する文字列のセットのセットであり、表現力の比較はこれらのセットを比較することです。
この分野における形式主義の相対的な表現力を説明する重要な基準は、チョムスキー階層です。これは、たとえば、正規表現、非決定性有限オートマトン、正規文法は表現力が同等であるのに対し、文脈自由文法の表現力はより優れていると述べています。これは、最初の 3 つの形式主義によって記述される文字列集合の集合が同等であり、文脈自由文法によって記述される文字列集合の集合の適切な部分集合であることを意味します。
この分野では、表現力のコストが研究の中心テーマです。たとえば、任意の 2 つの正規表現が同じ文字列セットを記述しているかどうかを判断するのは難しいですが、任意の文脈自由文法で同じことを行うのは完全に不可能であることが知られています。ただし、任意の文字列がそのセット内にあるかどうかは、効率的に判断できます。
より表現力豊かな形式主義の場合、この問題はより困難になるか、決定不可能になることもあります。任意の形式文法などのチューリング完全な形式主義の場合、この問題だけでなく、それらが記述する文字列の集合に関するすべての重要な特性は決定不可能であり、これはライスの定理として知られています。
簡潔性についてもいくつかの結果があります。たとえば、非決定性有限オートマトンと正規文法は、正規表現よりも簡潔です。これは、後者を前者にサイズの爆発なしで（つまりO(1)で）変換できるという意味で、その逆は不可能であるということです。
同様の考慮事項は、文字列のセットではなく、ツリー(例: XML スキーマ言語)、グラフ、またはその他の構造のセットを記述する形式主義にも適用されます。
データベース理論では
データベース理論は、とりわけ、データベース クエリ、たとえば、データベースの内容が与えられたときにそこから抽出する特定の情報を指定する数式に関係しています。主流のリレーショナル データベースパラダイムでは、データベースの内容は有限の数学的関係の有限集合として記述されます。常にtrueまたはfalseを返すブール クエリは、一階述語論理で定式化されます。
結局、一階述語論理は表現力が不足していることが判明しました。一階述語論理は、推移閉包を含むクエリなど、特定の種類のブールクエリを表現できません。[6]しかし、表現力を追加するには注意が必要です。クエリを妥当な効率で評価できる必要がありますが、これは二階述語論理 などには当てはまりません。その結果、多くのクエリ言語と言語構造を表現力と効率性に基づいて比較した文献が登場しました。たとえば、 Datalogのさまざまなバージョンなどです。[7]
同様の考慮事項は、他の種類のデータのクエリ言語、たとえばXQueryなどの XML クエリ言語にも適用されます。
参照
参考文献
- ^ Grau, Bernardo Cuenca; Horrocks, Ian ; Motik, Boris; Parsia, Bijan; Patel-Schneider, Peter; Sattler, Ulrike ( 2008 ). 「OWL 2: OWL の次のステップ」。Webセマンティクス: World Wide Web 上の科学、サービス、エージェント。6 (4): 309–322. doi :10.1016/j.websem.2008.05.001. ISSN 1570-8268.
- ^ ab ファーマー、ウィリアム (2007)。「カイロン：マルチパラダイム論理」。R. マトゥシェフスキ、A. ザレフスカ (編)。洞察から証明へ：アンジェイ・トリブレツを讃えた記念論文集。論理、文法、修辞学の研究。pp. 1–19。ISBN 978-83-7431-128-1。
- ^ コンピュータプログラムの構造と解釈、アベルソンとサスマン著
- ^ ab Felleisen, Matthias (1991-12-01). 「プログラミング言語の表現力について」.コンピュータプログラミングの科学. 17 (1): 35–75. doi : 10.1016/0167-6423(91)90036-W .
- ^ Okhotin, Alexander (2005年12月). 「未解決の言語方程式システム: 表現力と決定問題」.理論計算機科学. 349 (3): 283–308. doi : 10.1016/j.tcs.2005.07.038 .
- ^ Serge Abiteboul、Richard B. Hull、Victor Vianu：データベースの基礎。Addison-Wesley、1995年。
- ^ Evgeny Dantsin、Thomas Eiter、Georg Gottlob、Andrei Voronkov：「論理プログラミングの複雑性と表現力」ACM Comput. Surv. 33(3): 374-425 (2001)。