https://twitter.com/kinaba のログ (twilog の方が便利です。)
| あれ、これってちょっと式変形したら O(n^2) にならんかな https://t.co/mnLOsuNZ | |
| w'=c_{i-1}-1+c_j。 |M(w')|=|G(c_{i-1}-1)|+1。|G(w')|=|G(w'-c_{i-1})|+1=|G(c_j-1)|+1。よって |M(w')|<|G(w')| ⇔ |G(c_{i-1}-1)|<|G(c_j-1)|。なので (続く | |
| |G(c_k - 1)| を全ての k について最初に O(n^2) で求めておいたら、∃i,j さっきの最後の条件式、は O(n^2) でチェックできる。なにか勘違いしているかな。 | |
| 最小性を都合良く使いすぎているかもしれん。考えるるる | |
| ああさっきの自分の |G(w')|=|G(w'-c_{i-1})|+1 が猛烈にうそだ。c_{i-1} より高いコインで払えるようになっている場合がある（codeforcesにsubmitしてWAをもらうことによる検証手法）。よかったよかった | |
| "Reflection in the Chomsky hierarchy" http://www.cs.cornell.edu/~kozen/papers/papers_collapsed_chron.htm Kozen 先生が Barendregt と組んで異様に面白いことをやっている。何故こんな自然なアイデア今まで自分は考えなかったんだろう感満載だ。うおおおお | |
| .@sinya8282 http://www.cs.cornell.edu/~kozen/papers/papers_collapsed_chron.htm "Reflection in the Chomsky hierarchy" というdraft paperが（何の役に立つのかさっぱりすぎて格好いい等も含めて）面白かったのでお知らせ致します。 | |
| 「"English is rich enough to describe itself." インフォーマルな意味で、英語は英文法を英語で記述しきれるくらい強力だ。では、正規表現は"すべての正規言語の集合"自信をコーディングできるか？文脈自由言語なら？文脈依存言語は？」 | |
| 全部自己記述能力がないことが証明されるんだけど、万能チューリングマシンが書ける以上、Chomsky階層の一番上TMまで行けば自己記述能力はある。もっと弱い記述力のところで、自己記述できる言語クラスはあるのか？人工的に作ればある、と証明されるのだけど、自然にそういうのはある？ | |
| 面白いのが、任意の「言語クラスをエンコードした言語」を機械的にちょっと拡張して自己記述能力を持たせるのは可能という命題で、例えば停止問題とかだと停止判定オラクルを足すと元のマシンの停止問題は解けても、オラクル付き言語の停止問題は自身で解けない、となるけど、その無間地獄はないらしい | |
| Dexter Kozen の論文どれも面白いので皆様読むべし http://www.cs.cornell.edu/~kozen/papers/papers_collapsed_chron.htm 最近 coalebra に凝っているのかと思っていたら唐突に変なの混ぜてくる | |
| 自分は"トマト"の印象を頭に刷り込むことに成功してしまったので頭の中ではこんな風にレンダリングされてしまってまずいです。いや本当に http://gyazo.com/7bdf9536205f147d5d5403366eeed2cf RT @JapTagussan: オートマトンって聞くと未だに”マトン”の印象が表に出てしまってマズイ |