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

著者 : J.ホップクロフト J.ウルマン 野崎昭弘

• サイエンス社 (1986年3月1日発売)

感想・レビュー・書評

[exphenomenologueさんの感想 · 2014年8月28日]

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

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