https://twitter.com/kinaba のログ (twilog の方が便利です。)
| @USAGI_WRP 既に指摘されている通りですが、1962年没なのであれば、1963年1月1日から数えて50年がラインなのでは。 http://www.aozora.gr.jp/houkokusyo/shingai.html | |
| @USAGI_WRP とても素敵な試みだと思います。正式公開される日を楽しみにしています！(・∀・) | |
| http://www.youtube.com/das_captcha?next=/watch%3Fv%3DvYKtyKI1bMY このライブ版良いなあ。最初のアルバムと比べて入った年期が響く | |
| ここ数日読んでる本がどれも面白くて幸せなので26時まで起き続ける気力が湧いている | |
| これは寝るか… | |
| エア遅刻！3つめの発表から始めるか http://partake.in/events/2c878a3e-68c7-4415-9e8f-6011aa3122a8 #air_STACS | |
| もしかして：遅刻した最初の２つが一番専門に近かった | |
| 読めるのあるのかなこれ（何も考えてない） #air_STACS | |
| #air_STACS 「多角形の全域カバーする色つき監視点を置く、でも同色の監視点が複数みえる位置があっちゃダメ。最小何色？→O(log^2 n)」90度多角形の場合90度回る木みたいの作る、あまり凹すぎない場合でかい部分の縁を切って再帰塗りでlog n、てのをも一歩頑張る | |
| #air_STACS abstしか読んでないけどイベント列1個に対するモデル検査がPSPACEのロジックでもイベント列n個のshuffle演算に対するモデル検査だとnon-elementaryになりえます、とかかな。そりゃそうでは。（ちゃんと読みます） | |
| #air_STACS あ、n個じゃなくて2個の積でnonelementaryになるのか。へー。「プロセスの状態遷移図的なもの(スタックの状態遷移で表す)(BPA)の性質を表す割と単純なロジック(くりーね*だけある様相論理)(EF-logic)の真偽値評価はプロセス2本で凄く難い」 | |
| 次の次のセッションの左側とその次の右側が比較的読者フレンドリーなタイトルに見える | |
| @xhl_kogitsune 一応MSOまわりの研究で修論書いておりますので読めないと修士号が剥奪されてしまう… | |
| #air_STACS では https://t.co/sL20KegD の論文を現地で開催されているはずの時間に合わせて読んでエア実況をしております（説明口調） | |
| #air_POPL Ehrenfeucht-Fraïssé Game ってなんだっけ、あっちとこっちに石置き合うやつだっけ。Gameって書いてある論文は他の全ての単語と比べて難易度高い気がするのでいつも恐れおののいている気がしますね | |
| #air_STACS 「オートマトンで表せるハイパーグラフ（頂点＝文字列、辺＝文字の組上の正規言語）のbounded degreeな奴上の一階述語論理が3EXPTIMEとか」グラフ同士の同値を格好良く定めるE-F relをautomatic構造に格好良く応用したのが格好いいっぽい | |
| #air_STACS 、エアPOPLよりは自分はだいぶ理解できるんだけど他人に意味がわかるように140文字以内で発言するのが至難を極める。 | |
| #air_STACS なんとかかんとかセットカバーというのは問題はabstに書いてある通りで、LP！最大フロー！ランダマイズド！と頑張ると素晴らしい定数近似値比のアルゴリズムが出たらしい | |
| #air_POPL 「実数の加減乗除に関する論理は決定可能であることが（自然数だと無理なのに！）TarskiのQEという方法でできると知られてますが、論理の決定可能性というとオートマトンに落とすオートマトン狂メソッドも有名ですがそっちの手法ではできないの！？→できない」という論文 | |
| #air_STACS Field of Reals is not omega-Automatic これは面白かった。あとでちゃんと読もう。標数0の体がオートマトンメソッドで扱えるとするとなんかの同値類が有限個になるはずなんだけどならない矛盾みたいな証明。 | |
| @ikegami__ ある種の Abelian group のある種の等差数列がどうこうという定理 [Freiman66] が重要みたいなことが書いてあります（代数の香りを匂わせて @ikegami__ さんに詳細を読ませようメソッド | |
| @xhl_kogitsune "オートマトンちっく"と認識すればだいたい合ってます | |
| #air_STACS 整数計画を線形計画に緩和して解いた緩和解との差をパラメタにした計算量でvertex covertとか色々解くとか。これも結構面白い気がする。こっち方面全然知らないので新規性とかがよくわからないが。LP後の実装も重くなさそうなので実用的にどんなもんなんだろう。 | |
| #air_STACS 右の方は、グラフに関する性質を記述した論理式（「連結である」とか「赤い辺と黒い辺を交互にたどりつつ緑の頂点を避けながら無限に進める」とか）のモデル検査(実際にグラフ与えて満たすかどうか判定)や充足可能性(満たすグラフはあるか)等考える趣味の人たちがおりまして | |
| #air_STACS 論理式の表現力が強いほど難しい（けど、強いほど応用しがいがある）し、逆にグラフの方を簡単なものに制限する（平面グラフに限る）とかすると簡単になったり難しくもできたり。その辺の表現力を色々いじって巧い落としどころを見つけたり、 | |
| #air_STACS はたまた計算量評価の新しい手法を提案したり、とかそういう話達だと思います。MSOは普通のnot,and,or,forall,existsに加えてnodeやedgeの集合がforallとかexistsとか書ける論理。 | |
| #air_STACS automaticなんちゃらというのは、無限グラフを考えたいのだけど、無限なので全列挙とかできないので「頂点集合とか辺集合をオートマトンで表現できる」グラフに限って考えて色々するおはなしおはなし | |
| @xhl_kogitsune よいエアお店探して下さい | |
| ところで今頃昨晩のcodeforcesの結果確認した。C落ちてる…何故… | |
| 一部タグが air_POPL になってる投稿があるぞ俺！ #air_STACS | |
| Jamie Oliver さんって "focus on the User" https://t.co/aoQP1z4T で初めに名前を知ったのですけど、検索結果の例としてはこの方の名前を使う慣習でも最近あるんですか http://googlejapan.blogspot.com/2012/03/google.html | |
| @tsukuno POPLっていうノベルゲー作ってよ | |
| http://ecoop12.cs.purdue.edu/content/list-accepted-papers ECOOP、ヨーロピアンなのに北京なのか。あと"Is It Dangerous to Use Version Control Histories to Study Source Code Evolution?"結論が気になる | |
| せっかくだからこの右の赤のセッションを選ぶぜ #air_STACS | |
| #air_STACS 最近いたるところで見かける（言い過ぎ）Parysさんの論文だ。高階グラフ文法 (参考資料: エア論文紹介 http://t.co/doWiJisL) でできるグラフ上のpumping lemmaぽい物を示したよという論文。 | |
| #air_STACS こういう文法的なのは有限の記述で無限集合を表そうとするので何かの形で「繰り返し」が現れざるをえなくて、正規表現ならab*cみたいな単純な繰返しだし文脈自由文法ならv w^n x y^n zみたいな釣合の取れた繰返し構造があるというのがpumpingとかですが | |
| #air_STACS 今回のは高階pushdownの作れるグラフの上の十分長いパスが何かの正規言語に乗ってたらその正規言語に乗ったパスで無限に歩きを繰り返せるみたいなtheoremが書いてある。pumping lemmaはあると表現可能性の証明にとても便利なので良いことです | |
| #air_STACS implicit data structureは、「最初にこんにゃく食べようと思った奴」のコピペ並に最初にそんなことやろうとよく思ったな感があってすごいなーとよく思う。 | |
| #air_STACS https://t.co/kZeZQeh2 こういうラインの話で、オーダーn "unsafe" 高階文法に対応する高階オートマトンの作るグラフ構造で一階述語論理がn≧3から決定不能になるそうな。証明はPCPをエンコード。 | |
| #air_STACS PCPというのは http://d.hatena.ne.jp/ku-ma-me/20100724/p1 この難しいゲームのことです（再掲）（3度目）。"unsafe" のここでの意味は、高階関数の引数がオーダの高い順に並んでない事。(a->a)->a->aはsafeだがa->(a->a)->aはダメ | |
| #air_STACS この辺の高階なんちゃら（文法、スタック、パターンマッチ、ユニフィケーション、etc etc）が3とか4とか5とか中途半端なレベルから決定不能に化ける現象の名前が必要 | |
| #air_STACS 配列に対する区間の最頻値クエリを線形スペースで返すデータ構造。簡単バージョンはO(n+s^2)空間でO(n/s)時間。Lemma 2 (c=mode(A U B)&c notin A => c=mode(B))が使えるようにs個のブロック分け的な雰囲気？ | |
| #air_STACS Mastermind の論文は前に読んだやつだ。ヒット＆ブローするのに直前の問答1回しか問答を記憶できない奇病にかかってしまった人が、自分の全ての記憶を1回の問答にビット単位で押し込めることで明日の自分に伝える、涙なしには読めない感動巨編です。 | |
| #air_STACS どなたか「博士の愛した数式」をこの論文に基づいてリメイクして大ヒットさせましょう。 | |
| #air_STACS 赤セッションの方はクリックしたら違う論文がでてきた | |
| #air_STACS arXivにあった版を読んでる。large cardinal と game の determinacy がでてきてZFCから独立という話になってる。これは @ikegami__ さんじゃない方のイケガミダイスケ君を召還したい... | |
| #air_STACS 2人ゲームで、交互に文字をappendしあって、特定の文法にマッチするものが作れたら先手が勝ち、外せたら後手が勝ち、という無限ゲームの必勝法は「カウンタ1個＋有限状態オートマトンで受理できる言語」の場合でももっと一般の文脈自由言語並に難しいことの証明、 | |
| #air_STACS だそうだ。これも詳しくないので新規性度合いよくわからん。恐ろしそうな部分はだいたい既存研究の成果がそのまま引っ張れているだけなのであまり恐ろしくなかった。こけ脅し気味である。 | |
| やりましょう RT (via @oxy) 何故かstacsが流行っているが，これアルゴリズムの話とプログラミング言語の話と両方あって読者層が広いからかな．それだとICALPも流行りそう． | |
| @oxy 期待しております！ | |
| 最近STACSでプログラミング言語系の論文ってあんまり記憶にないので、ICALPの方が読みやすい人多そうな気がする。 |