焼肉

結局寝落ちして11時頃起床.昼飯はローストビーフ丼.久しぶりにsb研のnkmr君に会う.

「某大人気講義を受けてたら形式言語理論に興味が出てきた」という珍しい後輩がいるので,そりゃ頼もしいことだと,とりあえずオートマトンとか計算理論関係の本を無理やり貸し付けてみる.形式言語理論といえば,だいぶ前に正則言語と MSO (Monadic Second Order logic) と自由モノイドへの準同型の逆像がいい感じに対応しているという話しを聞いて興味深いなあと思ってたんだけども,まだ調べていない.いつかきっと後輩がその話を教えてくれるだろうということで.と言いつつ, MSOオートマトンの対応は自分の研究に使えるかもみたいな話しもあがっているので,そっちはさっさと調べるか.

計算可能性にしろそうなんだけど,多様な特徴づけをもつ数学的構造は扱いやすい.正則言語のクラスと帰納的可算な言語のクラスってある種その扱いやすいクラスの一番下と一番上という感じがするんだけど,何かここら辺を綺麗に述べることはできないんだろうか? 正則言語の下といえば Star-free language とかあるけど,この2つほど特徴づけが多様でないような気がする(自分が知らないだけな気もするけど).たとえば, star-free language のオートマトン的な特徴づけとかあるんだべかな? 帰納的可算よりも上はまあ言わずもがな魔境で,ここは個々のクラスに興味があるというよりも,クラス同士の関係性に興味がある話しだと理解している.Turing次数の理論とか全然わからんけどそういうことよね?

閑話休題.夜は焼肉.自分と直接は関係ないところの忘年会(?)になぜか混ざり込んだという感じだったが,まあ楽しくてよかった.それにしてもワンカルビ,量すごいな.