https://twitter.com/kinaba のログ (twilog の方が便利です。)
| あれ、まだおかしい | |
| なぜおかしいかというと定数項がない | |
| うわーこれはひどい | |
| @sacred_fox あってます。そして僕が激しく間違っています。ひー | |
| @sacred_fox @sawawww これでどうだ！（方程式の方も変えました。さっきのだとxもyも空集合だ） | |
| @sawawww 空集合+空集合+{空文字列} = {空文字列} になるので大丈夫だと思うんですが… | |
| @sawawww @sacred_fox @xhl 要するにあれは X ::= aX | bY | c あんど Y ::= bX | cY という文法が書いてあるだけなので | |
| @sawawww xからxに戻るパスじゃなくて、xから定数項に行くパスがxの表す言語で、yもyから定数項に行くパスがyの表す言語になります | |
| ぼろぼろや。 | |
| @sacred_fox はい。ですです。修正後の様に定数項を"c"のような文字にしてしまうと必ず最後に"c"が来る言語になっちゃいますけど、ax + "" = x みたいに空文字列を定数項におけば a* ができたり。しかし定数項が一つもないと何も受理できない… | |
| @xhl どうなるんですかね。僕も単純に正規表現の無限繰り返しの集合的なものになるかなあと思ったんですが、ax=x の解が今度こそ一意にならない（空集合と {aaa....}）といった現象が。 | |
| しちへんげ、最初にガガガーっと書きためたストックが明日で切れるので明後日からはなんか書かないといけない | |
| @syamino その辺りの対応に注視する分野の名前としては descriptive complexity とか implicit complexity でしょうか。 http://www.cs.umass.edu/~immerman/descriptive_complexity.html 。僕はあまり計算複雑性は詳しくないので適当ですけども | |
| @tsubosaka 見逃したままでもPTIMEで解けるかどうかが気になっているのですが、どんなもんですかね |