トップ «前の日(11-21) 最新 次の日(11-23)» 追記

日々の流転


2001-11-22

λ. 読書

「X」第17巻
CLAMP[著]
「天子な小生意気」第11巻
西森博之[著]
「少女革命ウテナ - 青の双樹」
ビーパパス・さいとう ちほ[原作] さいとう ちほ[イラスト]
Tags:

λ. X11R5 & exterm

/.Jの「国際化された XTerm を目指して」という記事のスレッドを読んで、X11R5の頃の事とかextermの事を知った。

というわけで、ftp://ftp.x.org/pub/R5/contrib-1.tar.Zをダウンロードしてきてextermのソースを入手。

過ぎ去った時間は取り戻せないし、これらが再び使われるようになることは多分無い。だからこそ、せめて記憶には留めておこうと思った。

λ. 今日の英語: use, boiled down

  • What's the use of being citizen, if you don't get equal right?
  • The editor-in-chief boiled down her lengthy report to just a few paragraphs.
Tags: 英語

2003-11-22

λ. 借りた本

『赤緑黒白』
『臨機応答・変問自在 2』
森 博嗣 [著]
『大人のための残酷童話』
倉橋 由美子 [著]
『犬儒派だもの』
呉 智英 [著]
Tags:

λ. コンパイラの作り方

抽象機械のコードを出力するところまで読んだ。そういえば、レジスタが足らなくなったらどうするんだろう。

本日のツッコミ(全2件) [ツッコミを入れる]

ψ ささだ [足りている気分になる.]

ψ さかい [ぎゃふん]


2004-11-22

λ. Bisimulation Algorithm

このままじゃ恥ずかしすぎるので、hyperset.rb(と未公開のHaskell版実装)を直そうと思いたったのだけど、また自分で考えると何か間違えそうなので、既存のアルゴリズムを探すことに。そこでGoogle先生に尋ねると A. Dovier, C. Piazza, and A. Policriti. A fast bisimulation algorithm. TR UDMI/14/00/RR, Udine, 2000. というのがあったので、これを使わせてもらおう。Non-Wellfounded な場合にはそうやってrankを定義できるのかぁ。なるほど、なるほど。

で、Haskellで試しにコードを書いてみようとしたのだけど、Paige-Tarjan の手続きを呼ぶとしか書かれてない部分があって困ってしまった。R. Paige and R. E. Tarjan. Three partition refinement algorithms. SIAM Journal on Computing, 16(6):973-989, 1987. に書いてるらしいのだが、この論文Web上にはないし、調べるの面倒なので、試しにこれ抜きでやってみる。幾つかの例を試すとこれでも正しく動作しているように見えるが……ダメな例を早速発見。Ω={Ω} として、α = {Ω,φ} と β = {Ω,φ,{Ω,φ}} が区別できないな。この二つは共にrankが1で、rankがこれより小さいのはrankが−∞のΩとrankが0のφ。α,βは共にΩとφを含んでいるので、Ωとφによる分割だけではα,βは区別できない。同じrank内でさらに分割する必要があるけど、それにはどうしたら良いのかなぁ。うーむ。

何が足りないのかとしばし悩んで(足りないのは Paige-Tarjan の手続きに決まってるけど)、{{Ω},{φ},{α,β}} という分割(によって定義される同値関係)はstableでないことに気付く。

ちなみに、関係R⊆N×Nが与えられたとき、Nの分割Pの任意のブロックB1,B2に対して、B1⊆R-1(B2)とB1∩R-1(B2)=φのいずれかが成り立つとき、Pは関係Rに関してstableだという。あるいは、分割Pによって定義される同値関係を≡Pとして、(∀a,a',b∈N)((a≡Pa' ∧ a R b) ⇒ (∃b'∈N)(b≡Pb' ∧ a' R b')) という定義の方が直観的かな。

閑話休題。さっきの例だと N = {Ω,φ,α,β}, R = ∋ なので、P = {{Ω},{φ},{α,β}} だと、B1 = B2 = {α,β} としたとき、R-1(B2) = {y | x∈{α,β}, y∈N, y ∋ x} = {β} となってしまい、Pはstableな分割ではないことがわかる。maximal bisimulation はstableであるはずなので、この同値関係は大きすぎる(i.e. 分割が粗過ぎる)ことが判定できる。試しにstabilizationの処理を素朴に実装して見たら、αとβは区別できるようになったし、試した限りでは他の例でも正しく動いているように見える。

ということは、Paige-Tarjan の手続きってのはstabilizationのための効率的なアルゴリズムのことなのかな? (ぉぃ

……とか書いてたら、バークレイ大のCS 294-1: Model Checking, EE 219C: Computer-Aided Verificationという授業の講義資料に Graph Minimization というのを発見。まだ読んでないけどとても良さそう。

あと、A fast bisimulation algorithm の著者のサイト にC++のコードがあるのも発見。


2005-11-22

λ. Naxos Music Library (ナクソス・ミュージック・ライブラリー)

弟に教えてもらったサイト。月額1,890円でクラシックを聴き放題。無料で15分間試すことが出来る。俺は音楽をあまり聴かないので月額1,890円というのは微妙だけど、クラシックをよく聴く人だったらよさげかも。

【2006-04-23追記】 SFCでなら keio.ml.naxos.jp で利用できるようになったらしい。

関連

Tags: 音楽

λ. A Cookbook for the Haskell XML Toolbox with Examples for Processing RDF Documents. Manuel Ohlendorf

をざっと読んだ。Haskell XML Toolbox (HXT) のデモンストレーションとしてRDF/XMLの処理を書く話。SPARQLのパーサ・処理系も実装してある。

λ. ELECOM LD-MCTF/BK2 携帯用ウルトラフラットLANケーブル(2m)

ELECOM 携帯用LANケーブル(ブラック)2m LD-MCTF/BK2

携帯するのに便利なLANケーブルが欲しかったので、ちょっと高いけど買ってみた。 なかなか便利。


2007-11-22

λ. OperaのiframeのcontentDocumentが変

MAD PEOPLE 用の発言ポップアップスクリプト が最近のOpera(Opera 9.21)で動かなくなっていたので調べたら、iframeの振る舞いが変わってしまっていた。 iframeからcontentDocumentでHTMLDocumentオブジェクトを取得し、その後そのiframeをremoveChildしたら、取得したオブジェクトがただのObjectになってしまって、HTMLDocumentとして操作できなくなってしまう。 昔のOperaはこんなことなかったんだけどなぁ。バグ?

ぐぐってみると、<URL:http://d.hatena.ne.jp/quaa/20070807#p1> に同じことが書いてあって、iframe.contentDocument.documentElement.ownerDocument として取得しておけば回避出来るようだ。

Tags: javascript

2009-11-22

λ. ダイビングのレッスン

(後で書く)