Loading article…
形式言語理論では、成長文脈依存文法とは、生成される文の長さが増加するような文脈依存文法のことである。 [1] [2]これらの文法は、したがって非縮約的かつ文脈依存的である。成長文脈依存言語は、これらの文法によって生成される文脈依存言語である。
これらの文法では、「開始記号」Sはどの生成規則の右側にも現れず、左側がSでない限り、各生成規則の右側の長さは左側の長さを超えます。[1]
これらの文法はダールハウスとワームスによって導入されました。[3]これらは後に非巡回文脈依存文法と同等であることが示されました。[3]任意の成長文脈依存言語への帰属は多項式時間で計算可能です。[4] [5]ただし、与えられた文字列が与えられた成長[6]または非巡回[ 7]文脈依存文法によって生成された言語に属するかどうかを判断するという統一的な問題はNP完全です。
参照
参考文献
- ^ ab G. Buntrock および F. Otto (1995)。「成長する文脈依存言語と Church-Rosser 言語」。Ernst W. Mayr および Claude Puech (編)。Proc . 12th STACS . LNCS. Vol. 900. Springer. pp. 313– 324. ISBN 978-3540590422。こちら: p.316-317
- ^ Gerhard Buntrock と Friedrich Otto (1998)。「成長する文脈依存言語と Church- Rosser言語」。情報と計算。141 : 1– 36。doi : 10.1006 /inco.1997.2681。
- ^ ab Gundula Niemann および Jens R. Woinowski (2002)。「成長しつつある文脈依存言語は非巡回文脈依存言語である」。Werner Kuich、Grzegorz Rozenberg、Arto Salomaa (編)。Proc . 5th Int. Conf on Developments in Language Theory (DLT)。Lecture Notes in Computer Science。Vol. 2295。Springer。pp . 197– 205。ISBN 978-3540434535。. ここ: p.197-198
- ^ E. Dahlhaus および MK Warmuth (1986)。「成長する文脈依存文法のメンバーシップは多項式である」。Paul Franchi-Zannettacci (編)。Proc. 11th Colloquium on Trees in Algebra and Programming (CAAP) (PDF)。LNCS。Vol. 214。Springer。pp. 85– 99。こちら: p.85-86
- ^ E. Dahlhaus および MK Warmuth ( 1986)。「成長する文脈依存文法のメンバーシップは多項式である」。Journal of Computer and System Sciences。33 ( 3): 456– 472。doi : 10.1016/0022-0000(86)90062-0。
- ^ G. Buntrock と K. Lorys。文脈依存言語の成長について。Proc. 19th ICALP、Lecture Notes in Computer Science (W. Kuich 編、77～88 ページ。Springer-Verlag、1992 年。
- ^ Erik Aarts (1992). 「文脈依存文法の統一認識は NP 完全である」(PDF) . Proc. 14th Int. Conf. on Computational Linguistics (COLING、ナント、8 月 23-28 日) . pp. 1157– 1161.
外部リンク
- G. バントロック: 文脈依存型言語の発展