Entries from 2009-01-01 to 1 year
この節は hybrid logic を first-order にする話。特別興味があるわけではなかったので軽く流し読みして済ませてしまいました。hybrid logic というのは様相論理に特定の世界でだけ真になる命題変数を付け加えた論理です。この命題変数を nominal と呼びます…
個体の解釈が可能世界ごとに違う意味論。単に object の解釈を世界に依存するように変えるだけかと思ったら、そうではなくて object と intention の二種類の sort を用意してます。 syntax intention variable (i, j, ...) が新たに term として加わります…
論理の意味論を二値で与えると modularity *1があることが多い(らしい)が、一方で analycity *2は失われる。逆に multi-valued matrix を使うと analycity が保障しやすい。この論文は multi-valued non-deterministic matrix が modularity と analycity の…
なんか Section 15 を読んでみたときのまとめが下書きに残っていたので公開しときましょう。余代数は代数の双対なのだけど、単純に双対をとるだけで対応するわけではない。実際これまでに扱ったような話では、必ずしもすべてが双対で対応付けられているわけ…
"Handbook of Modal Logic" の Chapter 9, First-order Modal Logic 読んでみようかなと思いました。Section 2 からが技術的な話。 意味論の定義 この節では、簡単な axiomatization をもつ三種類の意味論を与えています。 constant domain semantics: indiv…
解いてもらった。こうすればよいと。 □ □□□ □ ■□□ ■■■□ □ □□ ■ □■■■ ■■■■ ■□□□ ■■□■ ■■■■ ■■■■ T 字があるとできるんですね。なかったらできませんよね。たぶんそっちは証明できて、こうやって置いたとすると ■ ■■ ■ 左上を埋めるためにはこうするしかなくて…
sequent calculus から truth value を構築する話。技術的には既知なのだけど、この論文の焦点はそれをどう解釈するかにある。らしい。やってることは普通の sequent calculus から canonical model を作る標準的なやり方。Γ=>Δ が証明できない対 (Γ,Δ) で極…
参加してきました。してきましたが、問題読んだ時点で D-small 以外はどれも解ける気がしなかったりしてわりと残念でした。ちなみに D-small は問題をちゃんと読んだ人なら誰でも解けたんじゃないかと思うくらい簡単。*1 最初 20 分 とりあえず ABCD の順番…
GCJ の問題を解いていると、やっぱりグラフが苦手ということを感じるので『アルゴリズムC』のグラフアルゴリズムの部分を眺めたりしました。それで思ったことはいくつかあるのですが、アルゴリズムがどのようなコードで実現されるのかが見えていないという点…
ようやく論理の話が出てくる節なのですが、何というか、どこに感動すればいいのかよくわかりません。確かに coalgebra を使うことでそれらしい一般化はできているようなのですが、そんなに自然なやり方にも見えないし見通しがよくなった気もあまりしないし。…
24 あたりから最後まで。結局あんまり細かいところまで読み込んでないんですが、とりあえず。 計算量クラスの話。問題を他の問題に帰着するということ。 ハミルトン閉路と巡回セールスマン問題。TSP は NP なので最適解を見つけるのは非常に難しい。 そこで…
以下の三つの形のブロックを隙間なく並べて埋め尽くすことができる長方形は存在するか。 ■■ ■■ ■■ ■■ ■ ■■■ 答えは知りません。離散数学得意な人なら一瞬で解けそうな。
代数の variety に対応する、余代数の covariety の話。HSP theorem の余代数版をやります。ちなみに実際に本を読んでいるときは、図式を大量に描きながら計算しています。 homomorphic images 代数と同様に余代数にも準同型像というものが考えられる。定義…
昨日の続き。Ω は set functor で (や、その添え字のついたやつら) は Ω-coalgebra とします。 relation lifting ここからさらに圏論の香りが強くなります。嬉しい。関係 の relation lifting とは、図式 を Ω で写した から定まる の像のこと。これを と書…
代数の congruence に相当する bisimulation と behavioral equivalence について。圏論っぽい雰囲気が漂っていて楽しい節です。ほとんど set functor ですけど。*1以下、特に断らないかぎり Ω は set functor で は Ω-coalgebra とする。添え字や prime が…
終余代数 (final coalgebra) の基本的な話。終余代数とは、余代数の圏の終対象のこと。関手を fix するごとに定義される。理論はだいたい知ってるので例を中心に見ていく。 some examples black box machine . M が機械の内部状態で C が出力。状態遷移を起…
Vietoris functor の射への作用が well-defined である理由が本には一言も書いてなくて、しばらく考えてもわからなくて、おかしいなあと思ってたのですが、closed mapping lemma を使えばすぐできました。しばらく使ってなかったので存在を忘れていました。*…
余代数の入門。基本的な定義と例だけです。代数が演算子を計算することで構造を簡単にする仕組みを持っている (e.g. 1+2+3 -> 6)のに対して、余代数は単純なものを分解して構造を作り出す仕組みを持つ対象である、というようなことが書かれています。こんな…
110 前後で未解答のままになっていた比較的簡単そうなものをいくつか解きました。やり方はなんとなく思いついても、コードを書くのが面倒だなー、と思って放置していたものが多いのですが、書いてみればそんなに大変でもなかったりします。いきなりエディタ…
8.1 が tense logic で 8.2 が global modality & discriminator varieties というタイトル。詳細はフォローしないで軽く目を通しただけです。8.1 では、tense logic の future modality と past modality から adjoint が作れて、その結果これらの様相は必…
7.5 Canonical equations "Time to harvest."ようやく目的であった canonical equation の話になりました。でも細かいところはフォローしていない。等式を考えるので term が出てきます。代数を与えるときには term に現れる関数記号と代数の演算は一対一に…
真ん中あたりから読み始めて 23 章まで。Euler path/circuit の話が出てきて、それが存在するための必要十分条件とその証明。この部分は数学的帰納法の解説にページ数を割いてたりするので流し読み。次に、Euler circuit が存在しない場合に、複数回通る辺が…
本当は 1A に参加したかったのですが用事があったので、昨日の深夜の 1B に参加しました。結果からいうと 164 位で通過。(scoreboard: http://code.google.com/codejam/contest/scoreboard?c=186264#vf=1&sp=161)C はあまり解ける気がしなかったのと早く寝た…
7.4 Composite maps 今度は関数合成と canonical extension が可換になるかどうかという話。位相的な特徴づけをします。まず使う位相の定義。ブール代数の canonical extension の上で次の位相を考える。 : up-directed joins で閉じた down-set が閉集合 (S…
7.1 Introduction Section 7 は canonical equation の話。等式が canonical であるというのは、それがある BAO で成立するとき、その embedding algebra でも成立すること。論理の方では Kripke completeness に関係する。 7.2 Canonical extensions of Boo…
Section 6 Logics and varieties の続き。 6.3 Interpolation 基礎論サマースクールで聞いたような話。Craig interpolation proporty と superamalgamation property が対応する。superamalgamation から interpolation は Lindenbaum-Tarski algebra を考え…
Section 5 Frames and algebras の続きと Section 6 Logics and varieties の一部。 5.6 Class operations complex algebra をとる関手 と ultrafilter frame をとる関手 の関係について最初に触れられている。 これらの関手はいずれも全射を単射へ、単射を…
Section 5, Frames and Algebras. 途中 5.5 まで。 5.1 Introduction 有限な BAO に対し atom の集合の上にで関係を定義して frame を作ることができる。また、有限な frame が与えられたとき、その冪集合上に BAO の構造が自然に入る (complex algebra)。こ…
Handbook of modal logic の中にある "Algebra and Coalgebra" という章を読んでます。http://staff.science.uva.nl/~yde/papers/ac.pdf に、だいたい同じ内容のものが置いてあります。Section 4 は "Varieties of Expanded Boolean Algebras" というタイト…
結果はこんな感じになりました: http://www.go-hero.net/jam/09/name/k.kojimaどの問題も、基本的な知識があれば large まで解けるといったところ。Qualification Round にはちょうどいいレベルの問題じゃないかと思いました。A は特にアルゴリズムの知識が…