https://twitter.com/kinaba のログ (twilog の方が便利です。)
| http://link.springer.com/chapter/10.1007%2F978-3-540-95891-8_57 これも読んでて、発想面白いなーと思た。正規表現の結合,|,*という演算はある意味"正規表現からオートマトンへの変換が楽"。逆に理論的な形式言語の研究で追加演算として人気の&や否定は"変換しにくい"。ならばここで発想を変えて、(続 | |
| 続) 言語理論的にはプリミティブに見える&や否定を使おうとするよりむしろ、たとえ文字列集合として定義を書き下すといささか奇っ怪であろうとも、「正規表現からオートマトンへの変換処理」としてみると簡潔に書ける操作を正規言語ワールドに投げ込んで観察してみると楽しいのでは？？？という話 | |
| あと対32bit/64bit限定高速素数判定頑張った http://ceur-ws.org/Vol-1326/020-Forisek.pdf てのも読んだ。巧いwitnessとればそれぞれミラーラビン3発/7発で確実に判定できることが知られているわけだけど、最初にハッシュで擬素数を散らすことでそれぞれ1発/3発で倒す | |
| あと"演算子優先順位文法って実はすごかった" http://home.deib.polimi.it/crespi/OperPrecAndVPpropWithApp.pdf という論文面白かったんだけどこれ前に読んだ気がすごくするんだけどtwilogで出てこなかったのでメモっておく。続) | |
| 続)構文定義の他に、近年ではプログラム検証等にも文法を使う。後者では様々な集合演算で閉じてる(演算結果も同じ文法言語で書ける)のが重要で、その観点からVPLとか新しい言語クラスが提案されてるけど、よく考えたら演算子優先順位文法ってVPLの宣伝に使われる演算全部で閉じてたという話 | |
| 最近おもしろんぶん発見能力が低まっていてつらい | |
| @ranha ありがとうございます、読んだことありませんでした読みます！短いというのは良いことですね | |
| 短い論文いいですねといえば、わんこそば ならぬ わんこInformation Processing Letters http://www.journals.elsevier.com/information-processing-letters/ やりたい。後ろについた人が僕が論文読み終わるタイミングを見計らって次々と面白IPL論文を見繕って投げ込んでくれる会。 | |
| @sinya8282 急に4年前の話題をどうしたんですかww たしかにKMPとかAho-Corasickでいうところのfailure linkの指す先が違うというのがポイントなのでDFAが違うから、というのはそうですねえ。なるほど |