https://twitter.com/kinaba のログ (twilog の方が便利です。)
| @sinya8282 @ranha 見てないけどnがfixedなら直積とるのにn乗だから多項式だけどnもパラメタならサイズqのdfaがn個の時入力サイズqnに対し計算量q^nなのでこれはqnのどんな多項式でも押さえられない。qが定数の時はそうだしo(qn)ならだいたいなんでも | |
| ニュージーランド入国しての初めてのツイートがDFAの直積についてになってしまった | |
| @sinya8282 DFAの入力長ベース、の定義を詳しく…さっきのようなのが計算量理論的に普通の定義（=入力の可変部分をビット列にエンコードした長さの関数）だと思うのでそれ以外？ | |
| @sinya8282 Primality（与えられた正規言語が2つの非空な正規言語の結合で書けるか否か）とかPSPACE完全が最近証明されてた記憶が（不確か）。あと入力DFAが2つだとXMLとか検証でよく出てくるshuffle product取る系のだいたいやばそう | |
| @septef 日本より早いのもそうだが UTC+13（≧12）はなかなか格好いい | |
| 羊の国だ https://twitter.com/kinaba/status/558492063419748352/photo/1 | |
| $20か$50紙幣しか出ませんとあるATMで金額欄がテンキー自由入力だったので、ちゃんと可能な任意の額に対応してるか（100以上を50で出し下二桁を20で出そうとして20の倍数でなければ拒否する的実装でないか）検証したくなって$130にしたら正しく処理された。疑ってすまなかった | |
| そして$130も現金使う予定がまったくない | |
| @1_000_000_007 160ドルも現金使う予定がないので試してないのですが、さすがに普通にエラーを返してくれるのではないでしょうか | |
| @eomole 食べてみたいが絶滅危惧種と聞きました（鳥） | |
| Primality https://t.co/VF4ni3IYJ7 繋がりでなんとなく結合以外で同じ概念考える意味あるか考えてて「無限の正規言語は必ず２個の非空で互いに素な無限正規言語の和で書ける」とか証明してた。自明な気がするけど非自明な気もしてちょい面白いかもそうでもないかも | |
| ニュージーランドは港に謎の人間寝転がり用板が置いてあって人々が寝転がっていてよかった。 https://twitter.com/kinaba/status/558566471698497536/photo/1 | |
| 今日の宿からの眺めです（海からの距離のみを基準に泊まる場所を決める） https://twitter.com/kinaba/status/558566932215914497/photo/1 | |
| @septef 泊まる場所はホテル検索/予約サイトでヒットする有限個の点に限る物とする… |