https://twitter.com/kinaba のログ (twilog の方が便利です。)
| @kmizu @kagamilove0707 （最初のページの定理のステートメントしか呼んでないんですが）お二人同じことを言っているように聞こえます。二重指数時間で必ず計算が終わるのでチューリング完全じゃないと言っている | |
| https://t.co/noMhG9wrQI 読んだ。「3の倍数にマッチする正規表現」みたいな正規言語で定義できる自然数の集合とは数論的にどんな集合か、てのは既によくわかってる。文脈自由言語版はどうなん？という話。2次式ぽい条件も表せることもあるという例言われて見ればなるほどだ | |
| しかしこの論文だと結局あんまりよく特徴付けられてる感じはしないし、なんかもっと最近の研究でこの方向のないのかなと思って引用逆参照でたどろうと思ったがそもそも5件しか引用されてないし厳しい |