https://twitter.com/kinaba のログ (twilog の方が便利です。)
| @sinya8282 L={"abcba"} (文字列1つだけを受理する言語) 反例になりませんかね。Lに関してもFactorial(L)に関しても""とaとabとabcとabcbとabcbaは全て違う同値類に行くけど、Lはこれが全てで、Factorialでは"b"が更に異なる | |
| @sinya8282 L={w}のようなシングルトン言語だとLでの同値類は|w|+2個(wのprefixで割った物すべて=|w|+1個+空集合)で、Factorial(L)でもやはり同じように最低|w|+2個はあって、さっきのbみたいにそのどれとも違う物も作れそうという直感 | |
| #ゆる募 朝雨が降ってて夕方やんでても傘を持って帰るのを忘れなくなるライフハック （水曜日持ってきた傘がまだ職場に残っているのを眺めながら） | |
| @sinya8282 さっきまで二乗(≒元の最小DFAの状態ペア)では簡単に抑えられるんじゃないかという気がしていましたが気のせいだったかもしれませんがやっぱり成り立つ気もしています（非決定的予想）。 | |
| @septef 僕は真冬でも普通にコートを羽織るの忘れて帰って気づかない人間なので厳しめかもしれん… | |
| @fadis_ おおうジャパニーズサムライ | |
| @septef あっ、靴を履くの忘れて帰ったことはないので、靴を傘にかぶせておいておくのはありうる | |
| @mametter えっえっ | |
| @sinya8282 例は思いついてないですー。（abcbaに限らないでランダムな長い文字列のシングルトンに対してやってみるとどのくらい増えますかね。) | |
| @natsutan そうして今まさに置き傘が二本になってしまったので忘れず1本持ち帰らねばと考えているところなのです、、、 http://twitter.com/kinaba/status/299676899897118720/photo/1 | |
| 0123456789101112131415... っていう文字列ってなんか名前ついてそうだけど何か呼び方あったっけ。 | |
| @JapTagussan それ！ 実数じゃなくて単に(無限)文字列のことを考えていましたがチャンパーノウン定数といえば通じそうです。ありがとうございます！ | |
| @peria thanks! | |
| それで何が言いたかったかというと、チャンパーノウン定数の最初n桁のシングルトン集合を考えると、さきほどから @sinya8282 さんが考える問題の定数倍で抑えられない反例にならないか考えようとしていた | |
| @sinya8282 シングルトン集合以外での同値類の個数を数えられるほど頭が起きてないので、なんとか寝たまま反例がつくれないかさぼっているという思惑です（違 | |
| {1,12,123,1234,...,12345678910,1234567891011,...} は正規言語じゃないけどO(log log n)スペースで受理できる言語の例としてよく出てくる #さぶろぐ | |
| @sinya8282 {{},{正},{規},{言},{語},{正,規},{正,言},{正,語},{規,言},{規,語},{言,語},{正,規,言},{正,規,語},{正,言,語},{規,言,語},{正,規,言,語}} #パワーオブ正規言語を送ります | |
| @zakkas783 おおーしかし「ここまで来ちゃったら忘れ物に気づいても引き返すの面倒だから明日でいいやライン」と「トイレや昼食で机を離れる最大距離」との境界が結構微妙かもしれない… | |
| http://www.pllab.riec.tohoku.ac.jp/ppl2013/cat1-cat2-accepted.html PPL2013の採択論文一覧が出てた。森畑さんのがやっぱり圧倒的に面白そうだなあ。あと上里友弥さんがおる。今年もたぶん行ってみることにしよう | |
| しかし去年のPPLでgdgdと語っていた方向の研究っぽいこと何も進んでいないぞ。一年早いなあ… | |
| https://t.co/d0019cUR これをfavoった人とgeneralフローキラーの共同研究するというのはどうでしょうか | |
| TCO今年はRound間にすごい間おくんだな http://community.topcoder.com/tco13/algorithm/algorithm-rules/ 今月には始まるとは気づいてなかった |