オートマトン 言語理論 計算論 (2) (Information & computing (4))

  • サイエンス社
3.50
  • (0)
  • (1)
  • (1)
  • (0)
  • (0)
本棚登録 : 11
レビュー : 1
  • Amazon.co.jp ・本 (281ページ)
  • / ISBN・EAN: 9784781904320

感想・レビュー・書評

並び替え
表示形式
表示件数
  • 下巻では文脈依存文法を導入し、Chomsky階層を解説する。また、決定性文脈自由言語を導入するとともに、決定的言語と非決定的言語で差が出る事例を紹介する。言語の一般的定式を述べた後、いよいよ計算の複雑性の理論へ。もともとP=NPをめぐる話題が読みたくて読書を始めたので、ようやく到達した気分。

    その計算の複雑性に関しては初等レベルの記述としてよくできていると感じた。特に、異なる信託oracleを付加してP=NPの成否が変わってしまうという例(p.211-217)は、この問題がいかに解決が難しいかを示していて、とても面白い。次はPapadimitrouあたりを読むか。

全1件中 1 - 1件を表示

J.ホップクロフトの作品

オートマトン 言語理論 計算論 (2) (Information & computing (4))を本棚に登録しているひと

ツイートする