  |
はてなキーワード: 型理論とは
情報と存在の関係を数理化するために、高次圏論、ホモトピー型理論、および量子場の理論を統合した形式化を提案する。
まず、(∞,∞)-圏 C を考える。この圏の n-射は n 次元の情報構造を表現し、これらの間の高次の関係性を捉える。存在を表現するために、この (∞,∞)-圏上の (∞,∞)-シーフを考える。
(∞,∞)-シーフ F: C^op → (∞,∞)-Cat を定義し、これを「存在の超シーフ」と呼ぶ。ここで、(∞,∞)-Cat は (∞,∞)-圏の (∞,∞)-圏である。F(X) は対象 X に関連付けられた存在の可能性の (∞,∞)-圏を表す。
このシーフ F は以下の超層条件を満たす：
任意の対象 X と X 上の ∞-被覆 {U_i → X}_i に対して、以下の ∞-極限図式が (∞,∞)-圏の同値となる：
F(X) ≃ lim[∏_i F(U_i) ⇉ ∏_{i,j} F(U_i ×_X U_j) ⇛ ... ]
次に、ホモトピー型理論 (HoTT) の拡張として、∞-累積階層理論 (∞-CUT) を導入する。これにより、以下の型構成子を定義する：
さらに、高次 univalence 公理を採用し、以下を仮定する：
(A ≃^n B) ≃^(n+1) (A =^n B)
ここで、≃^n は n 次の同値関係を、=^n は n 次の同一性型を表す。
量子場理論の概念を取り入れるために、圏値場の理論を拡張し、(∞,∞)-圏値場 Φ: Bord^(∞,∞) → (∞,∞)-Cat を導入する。ここで、Bord^(∞,∞) は無限次元ボルディズム圏である。この場は以下の公理的場論の条件を満たす：
Φ(M ∐ N) ≃ Φ(M) ⊗ Φ(N)
Φ(∅) ≃ 1
Φ(M^op) ≃ Φ(M)^*
ここで、⊗ は (∞,∞)-圏の対称モノイダル構造を、* は双対を表す。
情報と存在の動的な相互作用を捉えるために、導来高次代数の概念を用いる。C の導来 (∞,∞)-圏 D(C) を考え、F の導来関手 LF: D(C)^op → D((∞,∞)-Cat) を定義する。情報の流れに沿った存在の進化は、以下の超越的余極限として表現される：
hocolim^∞_i LF(X_i)
最後に、情報と存在の根源的な関係を捉えるために、トポス理論を無限次元に拡張した ∞-トポスの概念を導入する。∞-トポス E = Sh^∞(C) 内で、存在を表す対象 Ω^∞ を定義し、これを無限次元部分対象分類子とする。
完備確率空間 (Ω, ℱ, ℙ) 上で、右連続増大フィルトレーション {ℱₜ}ₜ≥₀ を考える。
状態空間として、実可分ヒルベルト空間 ℋ を導入し、その上のトレース類作用素のなす空間を 𝓛₁(ℋ) とする。
システムダイナミクスを以下の無限次元確率微分方程式で記述する：
dXₜ = [AXₜ + F(Xₜ, uₜ)]dt + G(Xₜ)dWₜ
ここで、Xₜ ∈ ℋ は状態変数、A は無限次元線形作用素、F, G は非線形作用素、uₜ は制御変数、Wₜ は Q-Wiener プロセスである。
経済主体の最適化問題を、以下の抽象的な確率最適制御問題として定式化する：
ここで、𝓤 は許容制御の集合、L: ℋ × 𝓤 → ℝ は汎関数である。
価値汎関数 V: ℋ → ℝ に対する無限次元Hamilton-Jacobi-Bellman方程式：
ρV(x) = sup{L(x, u) + ⟨AX + F(x, u), DV(x)⟩ℋ + ½Tr[G(x)QG*(x)D²V(x)]}
ここで、DV と D²V はそれぞれFréchet微分と2次Fréchet微分を表す。
システムの確率分布の時間発展を記述する無限次元Fokker-Planck方程式：
∂p/∂t = -divℋ[(Ax + F(x, u))p] + ½Tr[G(x)QG*(x)D²p]
ここで、p: ℋ × [0, ∞) → ℝ は確率密度汎関数、divℋ はヒルベルト空間上の発散作用素である。
dλₜ = -[A*λₜ + DₓF*(Xₜ, uₜ)λₜ + DₓL(Xₜ, uₜ)]dt + νₜ dWₜ
ここで、λₜ は無限次元随伴過程、A* は A の共役作用素である。
価格過程の一般的な表現を、以下の無限次元マルチンゲール問題として定式化する：
Mₜ = 𝔼[M_T | ℱₜ] = M₀ + ∫₀ᵗ Φₛ dWₛ
ここで、Mₜ は ℋ 値マルチンゲール、Φₜ は予測可能な 𝓛₂(ℋ) 値過程である。
Girsanovの定理の無限次元拡張を用いて、以下の測度変換を考える：
dℚ/dℙ|ℱₜ = exp(∫₀ᵗ ⟨θₛ, dWₛ⟩ℋ - ½∫₀ᵗ ‖θₛ‖²ℋ ds)
インフレーション動学を、以下の無限次元確率偏微分方程式で記述する：
dπₜ = [Δπₜ + f(πₜ, iₜ, Yₜ)]dt + σ(πₜ)dWₜ
ここで、Δ はラプラシアン、f と σ は非線形作用素、iₜ は金利、Yₜ は総産出である。
小さなパラメータ ε に関して、解を以下のように関数空間上で展開する：
Xₜ = X₀ + εX₁ + ε²X₂ + O(ε³)
dwₜ = [Bwₜ + H(wₜ, πₜ, iₜ, Yₜ)]dt + K(wₜ)dWₜ
ここで、B は線形作用素、H と K は非線形作用素である。
金利上昇の実質賃金への影響は、以下の汎関数微分で評価できる：
δ𝔼[wₜ]/δiₜ = lim(ε→0) (𝔼[wₜ(iₜ + εh) - wₜ(iₜ)]/ε)
1. 非可換確率論：
量子確率論の枠組みを導入し、不確実性のより一般的な記述を行う。
経済均衡の位相的構造を分析し、均衡の安定性を高次ホモトピー群で特徴付ける。
4. 超準解析：
無限次元確率動的一般均衡モデルは、金利、インフレーション、実質賃金の相互作用を一般的な形で記述している。
モデルの複雑性により、具体的な解を得ることは不可能に近いが、この理論的枠組みは経済現象の本質的な構造を捉えることを目指している。
このアプローチは、金利上昇がインフレ抑制を通じて実質賃金に与える影響を、無限次元確率過程の観点から分析することを可能にする。
しかし、モデルの抽象性と現実経済の複雑性を考慮すると、具体的な政策提言への直接的な適用は不適切である。
このモデルは、経済学の理論的基礎を数学的に提供するものであり、実際の経済分析や政策決定には、この抽象的枠組みから導かれる洞察を、より具体的なモデルや実証研究と慎重に組み合わせて解釈する必要がある。
このレベルの抽象化は、現代の経済学研究の最前線をはるかに超えており、純粋に理論的な探求としての意義を持つものであることを付記する。
都市伝説によれば、かつてアインシュタインの古典的重力理論「一般相対性理論」を理解していたのは3人だけだったと言われている。
それが真実かどうかは別として、その3人のうちの1人がダフィッド・ヒルベルトである。彼は、今日の初学者でも一般相対性理論を理解できるように、それを数学で明確かつ正確（すなわち厳密）に形式化した。
古典的なアインシュタインの重力は、時空上の擬リーマン計量のモジュライ空間上のスカラー曲率密度汎関数の積分の臨界点の研究にすぎない。
物理学の基本的な理論は数学での基本的な定式化を持つべきだと信じたことで、ヒルベルトは本質的にアインシュタインを先取りすることができた。そのため、この汎関数は現在、アインシュタイン・ヒルベルト作用汎関数と呼ばれている。
ヒルベルトは、1900年の有名なヒルベルトの問題の一環として、この一般的なアイデアを以前から提唱していた。ここでヒルベルトの第6問題は、物理学の理論の公理を見つけることを数学者に求めている。
それ以来、そのような公理化のリストが見つかっている。例えば、
| 物理学 | 数学 |
| 力学 | シンプレクティック幾何学 |
| 重力 | リーマン幾何学 |
| ゲージ理論 | チェルン・ヴェイユ理論 |
| 量子力学 | 作用素代数 |
| トポロジカル局所量子場理論 | モノイダル(∞,n)-カテゴリ理論 |
このリストには注目すべき2つの側面がある。一方で、数学の最高の成果が含まれており、他方で、項目が無関係で断片的に見えることだ。
学生時代、ウィリアム・ローヴィアは「合理的熱力学」と呼ばれる熱力学の公理化の提案に触れた。彼は、そのような連続体物理学の基本的な基盤は、まず微分幾何学自体の良い基盤を必要とすることに気づいた。彼の生涯の出版記録を見てみると、彼が次の壮大な計画を追求していたことがわかる。
ローヴィアは、最初の2つの項目（圏論的論理、初等トポス理論、代数理論、SDG）への画期的な貢献で有名になった。なぜか、このすべての動機である3番目の項目は広く認識されていないが、ローヴィアはこの3番目の点を継続的に強調していた。
この計画は壮大だが、現代の基準では各項目において不十分である。
現代数学は自然にトポス理論/型理論ではなく、高次トポス理論/ホモトピー型理論に基づいている。
現代の幾何学は「変数集合」（層）だけでなく、「変数ホモトピー型」、「幾何学的ホモトピー型」、「高次スタック」に関する高次幾何学である。
現代物理学は古典的連続体物理学を超えている。高エネルギー（小さな距離）では、古典物理学は量子物理学、特に量子場理論によって精緻化される。
今日は朝から頭の中で魔法を数学的に抽象化することを考えてみたんやけど、これがまためちゃくちゃ深いんや。まず、魔法の呪文をバナッハ空間の作用素として考えるっちゅうのは基本やけど、これをさらに進めて、フォン・ノイマン代数の元として捉えてみたんや。ここでは、呪文を自己随伴作用素 T として、スペクトル分解を通じてその効果を解析するんや。これが無限次元空間での作用を考えると、スペクトル理論や作用素環論が絡んできて、ほんまに深遠やわ。
次に、変身術をリー群の作用として捉えるんやけど、これをさらに高次元の多様体上の微分同相群の作用として考えてみたんや。対象の集合 X 上の微分同相群 Diff(X) の滑らかな作用として、g ∙ x = y みたいに表現できるんやけど、ここでリー代数のエレメントを使って無限小変換を考えると、接束や微分形式が出てきて、微分幾何学的な視点がさらに深まるんや。ホンマに、変身術って奥が深いわ。
さらに、魔法の相互作用をホモトピー型理論と∞-カテゴリーを使って考えてみたんや。これを使うと、魔法は∞-グループイドの間の射として捉えられて、ホモトピー同値な空間の間の射として表現されるんや。例えば、呪文 f: A → B は対象 A を対象 B に変える射と見なせて、これがホモトピー同値やったら、逆射が存在するんやで。これを使って、魔法の可逆性とかを高次元のホモトピー理論の文脈で議論できるんや。
最後に、魔法のエネルギー保存をシンプレクティック幾何学の枠組みで考えると、エネルギーの変化をシンプレクティック多様体上のハミルトニアン力学系として解析できるんや。シンプレクティック形式 ω を使って、エネルギー E の時間変化を考慮すると、ハミルトンの方程式が出てきて、これが魔法の持続時間や効果を決定するんや。ほんまに、魔法って物理的にも数学的にも奥が深いわ。
今日はこんなことを考えながら、また一日が過ぎていったわ。魔法のことを考えると、なんや心が落ち着くんや。ほんまに不思議なもんやなぁ。
何かの参考とかにしたらダメです。書き始めて半年経つんだけどこっからどう直したらいいんだか（何をゴールにしたらいいのか）わからない。。
追記：合流性とか強正規化可能性とか停止性とか、全部チューリング不完全で、事前の静的解析で使うメモリの最大量が確定できる、とかそういう風に読み替えられる人を増やしたいのです、数式の添え字とΣと∫にびびらない人を増やしたいようなもので
数理論理学の一分野である証明論から成長した、数理論理学と理論計算機科学の境界領域の研究領域である型理論(type theory)は、大規模なプログラムの内的な整合性のチェックを行うための方法論を必要とする情報処理技術の分野で関心を集めている。
そもそも「型」(type)とは何か。プログラミング言語は一般的にはレコードや関数といったプログラムを構成する「値」(value)の定義をする道具である(*1)。その言語のコンパイラ作成者はこれらレコードや関数などの値、もしくは第一級の対象(first-class object)の種類を区別する型システム(type system)を必要とする。抽象代数学の観点からすると、「型」とはこれらの値もしくは第一級の対象が属する高階の対象(higher order object)としての空間(space)ないし代数系(algebraic system)で、型システムはそれら「型」とそれら相互の関係(relation)つまり型のなす順序構造(order structure)ないし束構造(lattice structrure)であるといえる。
プログラムを構成する値すべてに型が付くためには、曖昧でない(*2)こと、自己矛盾していないこと、悪循環を含まないこと、それぞれの値の内容をチェックするために無限の時間を要しない(*3)ことなどが必要で、これらを満たすなら、プログラムは有限時間で実行を終え、停止する。手続き型言語では無限ループ、型無しラムダ計算では無限再帰によって型付け不能なプログラムを書くことができるが、型理論はこれらのチューリング完全な計算機を意図しない停止しないプログラムから守る装甲でもあり、再帰やメモリ確保で好き勝手をさせないための拘束具でもある。型が付くプログラムには単に停止するというだけでなく、可能な実行経路（訂正：経路→方法）のすべてで同じ結果を出すなど種々の良い性質がある。
1)この定義は現実に使われているプログラミング言語の特徴を覆い切れていない、狭い不満足な定義だが本稿では都合上この定義に立脚して限定的に議論する。例えば変数(variable)というものを持つプログラミング言語もあり広く使われているが、これについてはレコードや関数と同じように性質の良いものとして扱うことが難しい。難しさの原因は次の注の内容と関連する。近年は変数を扱うかわりに値の不変のコピー(immutable copy)やその参照に名前を付ける機能を持つプログラミング言語が増えている。
2) 現実の情報システムでは、COBOL言語のレコード再定義やC言語の共用体、一般的な関数ポインタやVisual Basic言語のvariant型変数のように、同一領域に異なる型の値が共存する共用型(union type)の値がしばしば必要となる。共用型の値はgoto文を排除した構造化／オブジェクト指向プログラミングにおいて条件キャストやクラス分岐などによる実行経路の複雑さの主要な原因になるが、これは和型(sum type)すなわち相異なる型の非交和(disjoint sum)として定義することで曖昧さなく定義できる。
3) ゲームプログラムやネットワークサービスにおいてしばしばみられるように、入力として無限リストや任意に深い木のようなものを想定する場合には明らかに（条件を満たさない限り）停止しないことが正しい動作となり、この場合は最外周のループを（←どうする？）メモリリークを起こさないなど別の考慮が必要となる。
（株）はてな 6.59% 445352200円
毛利 裕二 5.98% 404128400円
梅田 望夫 4.30% 290594000円
伊藤 直也 1.79% 120968200円 ○
田中 慎司 1.30% 87854000円 ○
小林 直樹 1.15% 77717000円
お金の額面はともかくの話なんだけど、
○をつけたのは、はてなのコードを書いたことがあると"思われる人"。「名前 プログラミング」で検索して有意な結果が出た人に○つけた。各株主の詳細知りたい人は適当にググって
で、さらに
はてなの年収は524万円が平均年収です。（有価証券報告書調べ）
http://heikinnenshu.jp/joho/hatena.html
スクリプト言語（主に Perl/PHP/Python/Ruby/JavaScript）によるアプリケーション、ライブラリ開発の経験
ScalaやGoにおけるアプリケーション、ライブラリ開発の経験
iPhoneアプリ、もしくはAndroidアプリの開発経験
UNIX系OS、RDBMS （特に Linux、MySQL）についての基礎知識
コンピュータサイエンス（アルゴリズムとデータ構造、分散技術、自然言語処理技術、機械学習、データマイニング、型理論）に関する基礎知識
ネットワーク技術（HTTP、DNS、TCP/IPなど）についての基礎知識
大学卒／275,000円〜
http://hatenacorp.jp/recruit/fresh/application-engineer-entry
この毛利 裕二という人の持ち株の資産を新卒の給料(計算だるかったから計算からボーナス抜いたけど、手取り分で考えたらボーナス分くらいは消えるだろう)で稼ぐとしたら122年かかるし、梅田 望夫という人は88年かかる。本当にこの人たちにはそれほどの価値(上にあげた新卒に求めるやたらと高いスペック)分の価値があるのか？いや、価値があると思ったから株をあてがったんだろうけど...
まぁなんていうか...、はてなのエンジニアのみなさんお疲れ様です...業務がんばってください
↑new
「対象を具体的に構成することによって証明可能ならば, 存在しないと仮定して云々ではなく, 実際に構成したほうがよい」あるいは「(最狭義の)背理法なしでいけるならそうすべきだ」(これらは別の主張である)という主張なら意味は通りますが. もっともこの種の議論も教育云々に属すので.
彼の意味の非背理法証明は古典論理に従う通常の証明であり構成的証明や直観主義的な証明などとは異なる. だから直観主義的型理論の証明からrealizerとしてプログラムと正当性証明を抽出する話とか, 直観主義論理の存在具体化性なんかの話とは全く関係がない.
「機械的に書き換え可能なら情報量は変わらないのでは」という簡単な突っ込みもできる. 幾らかの人達は「とはいえ計算数学なんかでは背理法に依らない証明を考えるのは意味があるのでは」といったことを述べているが
件の著書の内容紹介に【「背理法による証明」を、格段に情報量の多い「背理法によらない証明」に機械的に書き換えることができる】とある. これは, 彼の意味の背理法による/よらない証明と, 古典論理/非古典論理による証明, または非構成的/構成的証明, との対比を混同している.
---
「LKもcut-free LKも非背理法的ということではないのか. そうだとするとカット除去定理は背理法除去とは無関係ではないのか.」
他方で彼の著書では竹内・八杉『証明論入門』を引用してカット除去定理が背理法除去を一般化した定理だとも主張している. ここでひとつ反論ができるとすれば「sequent calc.も非背理法的な証明体系ではないか. 証明に現れるsequentは全てvalidではないか.」
---
他方で彼のいう非背理法証明というのはそういう状況が起こらない証明をいう. Hilbert流の証明体系では途中にprovableなformulaしか現れないことを想像せよ. したがって彼の数学としての主張は「自然演繹とHilbert流の体系は同値. よって背理法は除去できる」
実際efqを用いた証明ではefqの適用の直前に矛盾が導かれているはずだから「途中に正しくない主張が現れる」という状況に適合している.
だから彼の拒否する証明法は広義の背理法よりももう少し広いものと考えられる. 例えばex falso quodlibetがnonsenseな証明法だと捉えていることは彼のサイトの記述から明らか.
正確にいうと彼のいう背理法は「否定導入と最狭義の背理法」を合わせたもの. 背理法を拒否する根拠は「背理法を用いた証明では途中に正しくない主張が現れる」こと. 自然演繹の証明図は途中にunprovableなformulaが現れることを想像せよ.
また「背理法を用いて証明できるなら用いないでも出来る」というのは彼の言葉の定義では正しいので「直観主義論理が云々, 派生規則だから暗黙に背理法が使われてる云々」は反駁にならない.
「教育の話だろ」という人間には「教育論の補強に数学を濫用しているし, 数理論理学の教科書まで出版している」と反駁しましょう.「それでも教育的な価値は云々」という人間には「教育論として批判しているのではなく数学として批判しているのだ」と反論しましょう.
適切に批判しないと「(最狭義の)背理法なしでは(通常の述語論理の形式的体系において)証明できない命題があるなどという人間は(彼の意味では背理法なしでも証明できるので)数理論理学を理解していない初心者である」などと云われて, 傾げる首を切り取られてしまった人間が賛同するので
型理論がどうとかCS的裏付けとか関係なくて、お前さんもperlcodesampleもプログラマーとしてどうしょうもなく未熟なんだよ。思い込みだけで間違ったことを書いているから、みんな間違っていると指摘しているだけだ。それなのに上から目線で偉そう言ってけしからんと言う。
理論的な裏付けがなくたって、動的型付けと静的型付けの優劣を議論するのが無意味なことは大人はみんな知ってる。どちらかが一方的にすぐれていると論じるのは未熟さの証だよ。理論的な勉強なんかいらないから、もっといろんなプログラミング言語でプログラムを書きなさい。成長した暁には自分が書いたことがどれほどくだらないことだったかわかるだろう。
静的型言語の課題は、十分強力な型推論を持ってる言語が実用プログラムを書くのにパラダイムシフトを要求する点なんだが、それよりなにより「なんだか怖い点」にあると思う。信奉者が「そんなことはない」と熱く否定するさまがますます怖い。
@yukihiro_matz さんは普通のユーザの声を代弁している。@perlcodesample さんが静的型付き言語を使う人々の餌食になったのも記憶に新しい。彼らは何を恐れ、既存のプログラミング言語を使う人々を攻撃し続けるのか。
型理論は先人から積み上げられたすばらしい理論体系だ。きちんと理解できる人は一部のエリートに限られ、こうしたエリート達の努力には本当に頭が下がるばかりだ。しかし、こうしたエリートのやってることは一般の人々からは評価されにくい。今、日本で有名な物理学者は誰か、名前を挙げられる人は居るだろうか。今、世界中の医学者達が力を注いでいるのはどのような研究だろうか。普通の人は答えられない。
彼らは努力している分、人から評価されることを求める。しかし、努力=評価となるほど世の中甘くはない。残念ながら、頭の良さ=評価ともならない。そのため、彼らは普通の言語を使う人々はいかに劣っており、自分たちが時間を費やしてきたことがいかに価値のあることかをアピールするために他者を攻撃する必要が出てくる。そうしなければアイデンティティを保てない。
彼らのやっていることが本当に価値があることならば、そこまで他者を否定しなくとも勝手に支持者が増えていくのではないか。彼らのやっていることが本当に正しいのであれば、静的型付き言語によって成功するプロダクトが幾多も現れ、その効果を自然と証明できるのではないか。彼らは、そうなっていない現状に焦りを感じ、恐れている。本当は静的型付き言語は実用的ではなく、自分たちの苦労は報われないのではないかと。
理論が美しいとか、エリートであるとか、そういうことだけでは必ずしも優遇されないのが社会の実情だ。静的型付き言語を使って、レガシーな命令型言語や動的型付き言語の欠点を暴露するような成果をどんどん出せばよい。
最後に、静的型付き言語の人々が忌み嫌う、動的型付き言語のコミュニティの言葉を送ることでこのエントリを締めくくろう。静的型付き言語で、正しいプログラムからなるきちんとした社会を実現してやろうじゃないか。
Shut the fuck up and write some code.
◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆
（追記）
これ、書いたのperlcodesample本人だろ
自演乙。
冤罪とか問題になってるご時世なので念のため言っておくけど、僕は@perlcodesample さんではない。上で下品な言い方をしたのでそこを批判されるのは当然だと思うけれど、言いたかったのは、ソフトウェアの世界は形式手法や型理論が全てではないわけだし、CS的な裏付けのないコード書いてる相手に対して一方的に自分の方が上の立場だと思わずに、もっと相手のやっていることを尊重して話をした方がいいってこと。
第1章 有限オートマトン D.Perrin：橋口攻三郎 1. 序論 2. 有限オートマトンと認識可能集合 3. 有理表現 4. Kleeneの定理 5. 星の高さ 6. 星自由集合 7. 特殊なオートマトン 8. 数の認識可能集合 第2章 文脈自由言語 J.Berstel and L.Boasson：富田 悦次 1. 序論 2. 言語 2.1 記法と例 2.2 Hotz 群 2.3 曖昧性と超越性 3. 反復 3.1 反復補題 3.2 交換補題 3.3 退化 4. 非生成元の探求 4.1 準備 4.2 生成元 4.3 非生成元と代入 4.4 非生成元と決定性 4.5 主錐の共通部分 5. 文脈自由群 5.1 文脈自由群 5.2 Cayleyグラフ 5.3 終端 第3章 形式言語とべき級数 A.Salomaa：河原 康雄 1. 序論 2. 準備 3. 書換え系と文法 4. Post正準系 5. Markov系 6. 並列書換え系 7. 射と言語 8. 有理べき級数 9. 代数的べき級数 10. べき級数の応用 第4章 無限の対象上のオートマトン W.Thomas：山崎 秀記 序論 Ⅰ部 無限語上のオートマトン 記法 1. Buchiオートマトン 2. 合同関係と補集合演算 3. 列計算 4. 決定性とMcNaughtonの定理 5. 受理条件とBorelクラス 6. スター自由ω言語と時制論理 7. 文脈自由ω言語 Ⅱ部 無限木上のオートマトン 記法 8. 木オートマトン 9. 空問題と正則木 10. 補集合演算とゲームの決定性 11. 木の単項理論と決定問題 12. Rabin認識可能な集合の分類 12.1 制限された単項2階論理 12.2 Rabin木オートマトンにおける制限 12.3 不動点計算 第5章 グラフ書換え：代数的・論理的アプローチ B.Courcelle：會澤 邦夫 1. 序論 2. 論理言語とグラフの性質 2.1 単純有向グラフの類S 2.2 グラフの類D(A) 2.3 グラフの性質 2.4 1階のグラフの性質 2.5 単項2階のグラフの性質 2.6 2階のグラフの性質 2.7 定理 3. グラフ演算とグラフの表現 3.1 源点付きグラフ 3.2 源点付き超グラフ 3.3 超グラフ上の演算 3.4 超グラフの幅 3.5 導来演算 3.6 超辺置換 3.7 圏における書換え規則 3.8 超グラフ書換え規則 4. 超グラフの文脈自由集合 4.1 超辺置換文法 4.2 HR文法に伴う正規木文法 4.3 超グラフの等式集合 4.4 超グラフの文脈自由集合の性質 5. 超グラフの文脈自由集合の論理的性質 5.1 述語の帰納的集合 5.2 論理構造としての超グラフ 5.3 有限超グラフの可認識集合 6. 禁止小グラフで定義される有限グラフの集合 6.1 小グラフ包含 6.2 木幅と木分解 6.3 比較図 7. 計算量の問題 8. 無限超グラフ 8.1 無限超グラフ表現 8.2 無限超グラフの単項性質 8.3 超グラフにおける等式系 8.4 関手の初期不動点 8.5 超グラフにおける等式系の初期解 8.6 等式的超グラフの単項性質 第6章 書換え系 N.Dershowitz and J.-P.Jouannaud：稲垣 康善，直井 徹 1. 序論 2. 構文論 2.1 項 2.2 等式 2.3 書換え規則 2.4 決定手続き 2.5 書換え系の拡張 3. 意味論 3.1 代数 3.2 始代数 3.3 計算可能代数 4. Church-Rosser性 4.1 合流性 4.2 調和性 5. 停止性 5.1 簡約順序 5.2 単純化順序 5.3 経路順序 5.4 書換え系の組合せ 6. 充足可能性 6.1 構文論的単一化 6.2 意味論的単一化 6.3 ナローイング 7. 危険対 7.1 項書換え 7.2 直交書換え系 7.3 類書換え 7.4 順序付き書換え 7.5 既約な書換え系 8. 完備化 8.1 抽象完備化 8.2 公平性 8.3 完備化の拡張 8.4 順序付き書換え 8.5 機能的定理証明 8.6 1階述語論理の定理証明 9. 書換え概念の拡張 9.1 順序ソート書換え 9.2 条件付き書換え 9.3 優先度付き書換え 9.4 グラフ書換え 第7章 関数型プログラミングとラムダ計算 H.P.Barendregt：横内 寛文 1. 関数型計算モデル 2. ラムダ計算 2.1 変換 2.2 計算可能関数の表現 3. 意味論 3.1 操作的意味論：簡約と戦略 3.2 表示的意味論：ラムダモデル 4. 言語の拡張 4.1 デルタ規則 4.2 型 5. 組合せ子論理と実装手法 5.1 組合せ子論理 5.2 実装の問題 第8章 プログラミング言語における型理論 J.C.Mitchell：林 晋 1. 序論 1.1 概論 1.2 純粋および応用ラムダ計算 2. 関数の型をもつ型付きラムダ計算 2.1 型 2.2 項 2.3 証明系 2.4 意味論と健全性 2.5 再帰的関数論的モデル 2.6 領域理論的モデル 2.7 カルテシアン閉圏 2.8 Kripkeラムダモデル 3. 論理的関係 3.1 はじめに 3.2 作用的構造上の論理的関係 3.3 論理的部分関数と論理的同値関係 3.4 証明論的応用 3.5 表現独立性 3.6 論理的関係の変種 4. 多相型入門 4.1 引数としての型 4.2 可述的な多相的計算系 4.3 非可述的な多相型 4.4 データ抽象と存在型 4.5 型推論入門 4.6 型変数をもつλ→の型推論 4.7 多相的宣言の型推論 4.8 他の型概念 第9章 帰納的な関数型プログラム図式 B.Courcelle：深澤 良彰 1. 序論 2. 準備としての例 3. 基本的な定義 3.1 多ソート代数 3.2 帰納的な関数型プログラム図式 3.3 同値な図式 4. 離散的解釈における操作的意味論 4.1 部分関数と平板な半順序 4.2 離散的解釈 4.3 書換えによる評価 4.4 意味写像 4.5 計算規則 5. 連続的解釈における操作的意味論 5.1 連続代数としての解釈 5.2 有限の極大要素と停止した計算 6. 解釈のクラス 6.1 汎用の解釈 6.2 代表解釈 6.3 解釈の方程式的クラス 6.4 解釈の代数的クラス 7. 最小不動点意味論 7.1 最小で唯一の解を得る不動点理論 7.2 Scottの帰納原理 7.3 Kleeneの列と打切り帰納法 8. プログラム図式の変換 8.1 プログラム図式における同値性の推論 8.2 畳込み，展開，書換え 8.3 制限された畳込み展開 9. 研究の歴史，他の形式のプログラム図式，文献ガイド 9.1 流れ図 9.2 固定された条件をもつ一様な帰納的関数型プログラム図式 9.3 多様な帰納的関数型プログラム図式 9.4 代数的理論 9.5 プログラムの生成と検証に対する応用 第10章 論理プログラミング K.R.Apt：筧 捷彦 1. 序論 1.1 背景 1.2 論文の構成 2. 構文と証明論 2.1 1階言語 2.2 論理プログラム 2.3 代入 2.4 単一化子 2.5 計算過程―SLD溶融 2.6 例 2.7 SLD導出の特性 2.8 反駁手続き―SLD木 3. 意味論 3.1 1階論理の意味論 3.2 SLD溶融の安全性 3.3 Herbrand模型 3.4 直接帰結演算子 3.5 演算子とその不動点 3.6 最小Herbrand模型 3.7 SLD溶融の完全性 3.8 正解代入 3.9 SLD溶融の強安全性 3.10 手続き的解釈と宣言的解釈 4. 計算力 4.1 計算力と定義力 4.2 ULの枚挙可能性 4.3 帰納的関数 4.4 帰納的関数の計算力 4.5 TFの閉包順序数 5. 否定情報 5.1 非単調推論 5.2 閉世界仮説 5.3 失敗即否定規則 5.4 有限的失敗の特徴付け 5.5 プログラムの完備化 5.6 完備化の模型 5.7 失敗即否定規則の安全性 5.8 失敗即否定規則の完全性 5.9 等号公理と恒等 5.10 まとめ 6. 一般目標 6.1 SLDNF-溶融 6.2 SLDNF-導出の安全性 6.3 はまり 6.4 SLDNF-溶融の限定的な完全性 6.5 許容性 7. 層状プログラム 7.1 準備 7.2 層別 7.3 非単調演算子とその不動点 7.4 層状プログラムの意味論 7.5 完全模型意味論 8. 関連事項 8.1 一般プログラム 8.2 他の方法 8.3 演繹的データベース 8.4 PROLOG 8.5 論理プログラミングと関数プログラミングの統合 8.6 人工知能への応用 第11章 表示的意味論 P.D.Mosses：山田 眞市 1. 序論 2. 構文論 2.1 具象構文論 2.2 抽象構文 2.3 文脈依存構文 3. 意味論 3.1 表示的意味論 3.2 意味関数 3.3 記法の慣例 4. 領域 4.1 領域の構造 4.2 領域の記法 4.3 記法上の約束事 5. 意味の記述法 5.1 リテラル 5.2 式 5.3 定数宣言 5.4 関数の抽象 5.5 変数宣言 5.6 文 5.7 手続き抽象 5.8 プログラム 5.9 非決定性 5.10 並行性 6. 文献ノート 6.1 発展 6.2 解説 6.3 変形 第12章 意味領域 C.A.Gunter and D.S.Scott：山田 眞市 1. 序論 2. 関数の帰納的定義 2.1 cpoと不動点定理 2.2 不動点定理の応用 2.3 一様性 3. エフェクティブに表現した領域 3.1 正規部分posetと射影 3.2 エフェクティブに表現した領域 4. 作用素と関数 4.1 積 4.2 Churchのラムダ記法 4.3 破砕積 4.4 和と引上げ 4.5 同形と閉包性 5. べき領域 5.1 直観的説明 5.2 形式的定義 5.3 普遍性と閉包性 6. 双有限領域 6.1 Poltkin順序 6.2 閉包性 7. 領域の帰納的定義 7.1 閉包を使う領域方程式の解法 7.2 無型ラムダ記法のモデル 7.3 射影を使う領域方程式の解法 7.4 双有限領域上の作用素の表現 第13章 代数的仕様 M.Wirsing：稲垣 康善，坂部 俊樹 1. 序論 2. 抽象データ型 2.1 シグニチャと項 2.2 代数と計算構造 2.3 抽象データ型 2.4 抽象データ型の計算可能性 3. 代数的仕様 3.1 論理式と理論 3.2 代数的仕様とその意味論 3.3 他の意味論的理解 4. 単純仕様 4.1 束と存在定理 4.2 単純仕様の表現能力 5. 隠蔽関数と構成子をもつ仕様 5.1 構文と意味論 5.2 束と存在定理 5.3 隠蔽記号と構成子をもつ仕様の表現能力 5.4 階層的仕様 6. 構造化仕様 6.1 構造化仕様の意味論 6.2 隠蔽関数のない構造化仕様 6.3 構成演算 6.4 拡張 6.5 観測的抽象化 6.6 構造化仕様の代数 7. パラメータ化仕様 7.1 型付きラムダ計算によるアプローチ 7.2 プッシュアウトアプローチ 8. 実現 8.1 詳細化による実現 8.2 他の実現概念 8.3 パラメータ化された構成子実現と抽象化子実現 8.4 実行可能仕様 9. 仕様記述言語 9.1 CLEAR 9.2 OBJ2 9.3 ASL 9.4 Larch 9.5 その他の仕様記述言語 第14章 プログラムの論理 D.Kozen and J.Tiuryn：西村 泰一，近藤 通朗 1. 序論 1.1 状態，入出力関係，軌跡 1.2 外的論理，内的論理 1.3 歴史ノート 2. 命題動的論理 2.1 基本的定義 2.2 PDLに対する演繹体系 2.3 基本的性質 2.4 有限モデル特性 2.5 演繹的完全性 2.6 PDLの充足可能性問題の計算量 2.7 PDLの変形種 3. 1階の動的論理 3.1 構文論 3.2 意味論 3.3 計算量 3.4 演繹体系 3.5 表現力 3.6 操作的vs.公理的意味論 3.7 他のプログラミング言語 4. 他のアプローチ 4.1 超準動的論理 4.2 アルゴリズム的論理 4.3 有効的定義の論理 4.4 時制論理 第15章 プログラム証明のための手法と論理 P.Cousot：細野 千春，富田 康治 1. 序論 1.1 Hoareの萌芽的な論文の解説 1.2 C.A.R.HoareによるHoare論理のその後の研究 1.3 プログラムに関する推論を行うための手法に関するC.A.R.Hoareによるその後の研究 1.4 Hoare論理の概観 1.5 要約 1.6 この概観を読むためのヒント 2. 論理的，集合論的，順序論的記法 3. プログラミング言語の構文論と意味論 3.1 構文論 3.2 操作的意味論 3.3 関係的意味論 4. 命令の部分正当性 5. Floyd-Naurの部分正当性証明手法とその同値な変形 5.1 Floyd-Naurの手法による部分正当性の証明の例 5.2 段階的なFloyd-Naurの部分正当性証明手法 5.3 合成的なFloyd-Naurの部分正当性証明手法 5.4 Floyd-Naurの部分正当性の段階的な証明と合成的な証明の同値性 5.5 Floyd-Naurの部分正当性証明手法の変形 6. ライブネスの証明手法 6.1 実行トレース 6.2 全正当性 6.3 整礎関係，整列集合，順序数 6.4 Floydの整礎集合法による停止性の証明 6.5 ライブネス 6.6 Floydの全正当性の証明手法からライブネスへの一般化 6.7 Burstallの全正当性証明手法とその一般化 7. Hoare論理 7.1 意味論的な観点から見たHoare論理 7.2 構文論的な観点から見たHoare論理 7.3 Hoare論理の意味論 7.4 構文論と意味論の間の関係：Hoare論理の健全性と完全性の問題 8. Hoare論理の補足 8.1 データ構造 8.2 手続き 8.3 未定義 8.4 別名と副作用 8.5 ブロック構造の局所変数 8.6 goto文 8.7 （副作用のある）関数と式 8.8 コルーチン 8.9 並行プログラム 8.10 全正当性 8.11 プログラム検証の例 8.12 プログラムに対して1階論理を拡張した他の論理 第16章 様相論理と時間論理 E.A.Emerson：志村 立矢 1. 序論 2. 時間論理の分類 2.1 命題論理 対 1階述語論理 2.2 大域的と合成的 2.3 分岐的 対 線形 2.4 時点と時区間 2.5 離散 対 連続 2.6 過去時制 対 未来時制 3. 線形時間論理の技術的基礎 3.1 タイムライン 3.2 命題線形時間論理 3.3 1階の線形時間論理 4. 分岐的時間論理の技術的基礎 4.1 樹状構造 4.2 命題分岐的時間論理 4.3 1階の分岐的時間論理 5. 並行計算：その基礎 5.1 非決定性と公平性による並列性のモデル化 5.2 並列計算の抽象モデル 5.3 並列計算の具体的なモデル 5.4 並列計算の枠組みと時間論理の結び付き 6. 理論的見地からの時間論理 6.1 表現可能性 6.2 命題時間論理の決定手続き 6.3 演繹体系 6.4 モデル性の判定 6.5 無限の対象の上のオートマトン 7. 時間論理のプログラムの検証への応用 7.1 並行プログラムの正当性に関する性質 7.2 並行プログラムの検証：証明論的方法 7.3 時間論理による仕様からの並行プログラムの機械合成 7.4 有限状態並行システムの自動検証 8. 計算機科学における他の様相論理と時間論理 8.1 古典様相論理 8.2 命題動的論理 8.3 確率論理 8.4 不動点論理 8.5 知識 第17章 関係データベース理論の構成要素 P.C.Kanellakis：鈴木 晋 1. 序論 1.1 動機と歴史 1.2 内容についての案内 2. 関係データモデル 2.1 関係代数と関係従属性 2.2 なぜ関係代数か 2.3 なぜ関係従属性か 2.4 超グラフとデータベーススキーマの構文について 2.5 論理とデータベースの意味について 3. 従属性とデータベーススキーマ設計 3.1 従属性の分類 3.2 データベーススキーマ設計 4. 問合わせデータベース論理プログラム 4.1 問合わせの分類 4.2 データベース論理プログラム 4.3 問合わせ言語と複合オブジェクトデータモデル 5. 議論：関係データベース理論のその他の話題 5.1 不完全情報の問題 5.2 データベース更新の問題 6. 結論 第18章 分散計算：モデルと手法 L.Lamport and N.Lynch：山下 雅史 1. 分散計算とは何か 2. 分散システムのモデル 2.1 メッセージ伝達モデル 2.2 それ以外のモデル 2.3 基礎的概念 3. 分散アルゴリズムの理解 3.1 挙動の集合としてのシステム 3.2 安全性と活性 3.3 システムの記述 3.4 主張に基づく理解 3.5 アルゴリズムの導出 3.6 仕様記述 4. 典型的な分散アルゴリズム 4.1 共有変数アルゴリズム 4.2 分散合意 4.3 ネットワークアルゴリズム 4.4 データベースにおける並行性制御 第19章 並行プロセスの操作的および代数的意味論 R.Milner：稲垣 康善，結縁 祥治 1. 序論 2. 基本言語 2.1 構文および記法 2.2 操作的意味論 2.3 導出木と遷移グラフ 2.4 ソート 2.5 フローグラフ 2.6 拡張言語 2.7 その他の動作式の構成 3. プロセスの強合同関係 3.1 議論 3.2 強双模倣関係 3.3 等式による強合同関係の性質 3.4 強合同関係における置換え可能性 3.5 強等価関係上での不動点の唯一性 4. プロセスの観測合同関係 4.1 観測等価性 4.2 双模倣関係 4.3 観測合同関係 4.4 プロセス等価性上での不動点の唯一性 4.5 等式規則の完全性 4.6 プロセスの等価性に対するその他の概念 5. 双模倣等価関係の解析 5.1 等価性の階層構造 5.2 階層構造の論理的特性化 6. 合流性をもつプロセス 6.1 決定性 6.2 合流性 6.3 合流性を保存する構成子 7. 関連する重要な文献
