解いてもらった。こうすればよいと。 □ □□□ □ ■□□ ■■■□ □ □□ ■ □■■■ ■■■■ ■□□□ ■■□■ ■■■■ ■■■■ 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 は特にアルゴリズムの知識が…

去年は実行用のスクリプトを用意していたんですが、バグが出たときにアドホックなテストがやりにくくなってた気がするので今回はあまりそういうことはしないつもりです。あと去年は環境の整っていない windows でやってました。このままだと今年も同じ環境に…

今日の朝 8:00 からスタート。8:40 ごろから始めて、昼の 12 時過ぎに解答を提出し終えました。コードを書くのに時間かかりすぎ。

神戸大で講演があったので、一回分余っていた青春 18 きっぷを消費しつつ行ってきました。往復するだけだとあんまり有効に使った気がしないので、奈良に寄り道しました。それでも三千円分も乗ってないと思いますが。奈良駅の周辺を歩き回ったり、JR 六甲道駅…

昨日から SLACS 2009 に参加してました。全体的な印象として、今年は講演のレベルが高かったように感じました。内容が高レベルというのもそうですが、それよりも印象的だったのは、発表がわかりやすくてよく知らない分野の話でもだいたいの内容は理解できた(…