オートマトン 言語理論計算論II

書影

Information & Computing  4

オートマトン 言語理論計算論II

定価:
3,098
(本体:2,816円+税)

発行日:1986年3月1日

発行:サイエンス社

ISBN:978-4-7819-0432-0

サイズ:並製A5

ページ数:296ページ

在庫:品切れ

内容詳細

オートマトン,言語および計算理論の入門書として高い評価を得ている書の翻訳版.

目次

1 Chomskyの階層
1-1 正則文法
1-2 一般の文法
1-3 文脈依存言語
1-4 言語のクラス間の関係
1-5 演習問題
1-6 演習問題への解答
2 決定性文脈自由言語
2-1 DPDAの標準形
2-2 DCFLの補集合のもとでの閉包性
2-3 予知機械
2-4 DCFLの他の閉包性
2-5 DCFLの決定問題
2-6 LR(0)文法
2-7 LR(0)文法とDPDA
2-8 LR(k)文法
2-9 演習問題
2-10 演習問題への解答
3 言語族の閉包性
3-1 トリオと強トリオ
3-2 GSM(汎順序機械)写像
3-3 トリオに関するその他の性質
3-4 言語の抽象族
3-5 AFL演算の間の独立性
3-6 まとめ
3-7 演習問題
3-8 演習問題への解答
4 計算の複雑さの理論
4-1 定義
4-2 線型加速,テープ圧縮,テープ数削減
4-3 階層定理
4-4 計算量の測度の間の関係
4-5 移行補題と非決定性の階層
4-6 計算量の測度に関する一般的な性質:間隙定理,加速定理,和定理
4-7 公理論的な計算量の理論
4-8 演習問題
4-9 演習問題への解答
5 手におえない問題
5-1 多項式時間と多項式領域
5-2 いくつかのNP完全問題
5-3 補NP
5-4 PSPACE完全問題
5-5 TとNSPACE(LOGn)に対する完全問題
5-6 手におえないことが証明可能ないくつかの問題
5-7 神託つきテューリング機械に対するT=NT問題:T=NTの成否を知るために必要なわれわれの能力の限界
5-8 演習問題
5-9 演習問題への解答
6 他の重要な言語
6-1 補助テープつきプッシュダウン・オートマトン
6-2 スタック・オートマトン
6-3 インデックス言語
6-4 成長システム
6-5 まとめ
6-6 演習問題
6-7 演習問題への解答

サポート情報

関連書籍

CによるフラクタルCG

渕上季代絵

1,760円(税込)

中級
COBOLの基礎と応用

大駒誠一

1,595円(税込)

入門
情報数理入門

大矢雅則井上 啓佐藤圭子

2,068円(税込)

中級