https://twitter.com/kinaba のログ (twilog の方が便利です。)
| @sinya8282 最小DFAに対して、同じ言語を受理するサイズ最小NFAからSubset構成で作ったDFAのサイズ上限、てことですよね。うーむ特に知らないです面白そう。DFAのreverseなNFAからは冪構成で最小DFAが得られる定理の横になんか書いてあったりしないかな… | |
| こういうの確かに色々な問題で気になっていて、「この問題を解く計算量はO(f(n))になる」っていうのの証明が出力のサイズがθ(f(n))になる例があるから、で済まされているとそういうことを聞いてるんじゃねぇ、っていう気分になる | |
| @sinya8282 NFAに何か制限を入れないと、DFAに対してsubset constructionすると同じDFAが出てくる(というのが僕の中でのs.c.の定義によると成り立つのですけど)ので、無駄にでかいDFA(に偶然なってるNFA)から始めると幾らでも大きくできませんか | |
| @sinya8282 あ、でも、「_subset constructionすると指数オーダでサイズが増えるけど_minimal DFAを取ると指数オーダで増えてない」ようなNFAの族はあるか、みたいな問いにすると最小にNFAを限らなくてもよいかも | |
| @sinya8282 http://www.cse.unsw.edu.au/~rvg/pub/nfadfa.pdf あった "NFAs for which subset construction ... generates a DFA that is much larger than the minimal DFA." | |
| @sinya8282 NFA→DFAの指数爆発が避けられないことがあるっていう例の説明でよく出てくる (0|1)*0(0|1)^n に対応するNFAの初期状態を受理状態に変えたNFAからsubset構成すると依然として指数に増えるけど最小DFAは1-state、とのこと | |
| やっぱり最小NFAを取らないと単純なsubset constructionはいくらでも騙せてしまう…？ | |
| @sinya8282 あ、はい、そうです。https://t.co/fmkm7N9n を考えていました。最小NFAは依然として謎です。ただこの例を見ていて思ったのは、subset constructionは受理状態に依存しないので最小NFAでもその辺突けそう…？ | |
| subset construction派とpowerset construction派の戦い #オートマトンあるある #ない | |
| @sinya8282 おおおーやりましょう。僕の方は22,23,24,28が忘年会的なものとプログラミングコンテスト的なもので埋まっちゃってるのですが、25日以降は平日でも暇です。いちおう来週も木曜日以外はどうにかなる系です | |
| へび〜 ~>゜)～～～ http://twitter.com/kinaba/status/279837054748205058/photo/1 | |
| ジャパンヘビセンターに来ています。 http://twitter.com/kinaba/status/279837699840552960/photo/1 | |
| http://snake-center.com/ ジャパンスネークセンター、全国の違法毒ヘビマニアから押収された蛇の展示がかなりの割合あってなんかおもしろかった。あと採毒実演の研究員さんの解説しゃべり普通に楽しかったので行く人は時間狙って行くべき | |
| @finalfusion はいーどれの話でしょう | |
| きのこの山とたけのこの里について論じている人、適当言ってて前回論じたときに自分がどっち派だったか忘れてたりしないんだろうか、みたいなことがいつも気になる | |
| .@tsukuno @kamo_hiroyasu @xhl_kogitsune それは失礼いたしました | |
| 青春アルゴリズムでググった時の1位はそういうもんなんですか http://gyazo.com/b7a72d2d60b7899d2279aa57be8e1fa1 | |
| 24日の朝なら23に実家帰るついでに泊まって見てくのありかなあと考えている | |
| @lyrical_logical @finalfusion それりりろじさんが詳しいですって返事しようとしたらする前に来た！わーい | |
| @kyuridenamida じぶんちにテレビないので放送時間調べて実家にURL送って録画頼もうと検索したらこれですよ。 | |
| @finalfusion さんがどの辺気になってるのかわからんので勝手なオススメですけど、まずカタとかカテとかわけわからんので値レベルの話で入ると面白いと思ってて、つまりopen recursionでぐぐって最初に出る日本語記事が良いと思います @lyrical_logical | |
| @finalfusion @lyrical_logical それでそういえば型コンストラクタもただの型to型の関数なんだから全く同じことができるんだなあ…というのをその論文読むまで全く考えてなかったので面白くなって以下論文の内容まったく関係なく暴走したのが僕の例の日記です | |
| @finalfusion @lyrical_logical それがまさに http://d.hatena.ne.jp/lyrical_logical/20111107/1320671610 に書いてあります！ | |
| さぶろぐ本 http://www.amazon.co.jp/dp/3540583556 面白かった。入力長 n まで数を数えることすらできない抑え込まれた計算機が、log n までなら数えられることを利用して log n 以下の moduloscope を通して世界を探る技巧 | |
| clopen recursion |