https://twitter.com/kinaba のログ (twilog の方が便利です。)
| https://t.co/YLCc9PAdZ6 ハイパーグラフというか関係DBに対するクエリ言語は表現力豊かにしすぎると色んな性質(ここでは特に2個のクエリの返す結果が常に包含関係かの判定)が決定不能なので、そうならない範囲でギリギリまで表現力上げようというチキンレースがあって | |
| https://t.co/YLCc9PAdZ6 MDlog:古くから決定可能な言語として研究されてるいわばベースライン、MQ+:MDlogの拡張(著者らの研究)、GDlog:MDlogの別の拡張、があったが両方の拡張を合わせてもまだ決定不能崖から落ちなかったぜというお話に読める | |
| MQ+やGDlogの個々の拡張はそれぞれ確かに新しくて面白いと思うんだけど、それを単純に両方同時に突っ込んでもやればできたと見えるので、state-of-the-artを先に伸ばしたという意味で価値はあるんだろうけど面白さ的にどうなんというのが素朴な感想（ちゃんと読むと違うかも | |
| RT @tmaehara: Distinguish3: Reasonable highly expressive query languages http://ijcai.org/papers15/Papers/IJCAI15-400.pdf @sinya8282氏や@kinaba氏が得意そうな話っぽい（教えてくれたら嬉しいな… | |
| ちなみに自分の専門は主にグラフというより木なので、木ならこの辺の表現力のクエリ言語だと軒並み瞬殺で決定可能なので、いやーグラフは大変ですなあという気分で読んでいます | |
| 決定可能であることがわかるのが一般理論に帰着して瞬殺なのであって、実際決定する計算は瞬殺ではない（なんとかEXPTIMEとかにはすぐなる）（NP完全であることがわかったらやったーこれは実用的に解ける問題だバンザイみたいな気分になる人も多いくらいの世界） | |
| 「表現力の強い言語で表現した集合⊆弱い言語での集合」の判定よりも「弱い⊆強い」の方が難しいことが多い（文脈自由言語⊆正規言語とか、さっきの論文でのDatalog⊆制限Datalogとか）のは何故だろ。補集合とれば逆転するので、人類が補集合とらない側を好むのは何故かという疑問になる | |
| @john_229 まあまあかぜ | |
| @john_229 論文を読むと体が休まるという説があります | |
| @john_229 はい | |
| RT @mickey24: A: What's AFAIK? B: IIRC as far as I know A: IIRC? B: If I recall correctly. HTH A: HTH? B: Hope this helps A: TIL, AFAIK, II… | |
| あとは有限モデル理論おもしろいですよねトークは新屋さんが繰り広げてくれると思いますね | |
| https://t.co/jcDuqeAG8W Wikipediaの有限モデル理論のところに書いてあるZero-One Lawの記述がおかしいのだけど何をどう解釈してこうなったんだろう。多項式時間でチェック可能な任意のグラフの性質がzero-one lawを満たすわけがない |