kinaba 読んだ - 昏論会ウィキ

読んだもの

• A linear translation from CTL* to the first-order modal μ-calculus

• Relationships Between Nondeterministic and Deterministic Tape Complexities

• CIAA 2010 流し読み。多少ちゃんと読んだのが:
  • SVMの学習の話
    • Rational Kernelという、要は重み付き文字列transducerで計算できるKernelでSVMするときの学習アルゴリズムをオートマトン的に作った話
    • Kernelの定義がこれだからそりゃそうだねという感じ
  • ケーリーハミルトンの定理：非可換半群の場合
    • 引き算がないのは自然数から整数 / 整数から有理数を作るときと同じ構成でどうにかする。可換性は ab+ba という演算を入れてどうにかする。
  • A Polynomial Time Match Test for Large Classes of Extended Regular Expressions

• On randomizing two derandomized greedy algorithms

• The set constraint/CFL reachability connection in practice

• Strong Normalization of Classical Natural Deduction with Disjunction
  • 型付きλ計算の停止性を順序関係で証明できるかという話繋がりで
  • タイトル通り。古典論理的な自然演繹のSNの証明で、古典っぽい方のreductionはtermに入れた自然数重みが単調減少していくことで止まることが示せて、直観主義っぽいreductionは単純型付きλ計算のSNに帰着できる

• Meta Optimization: Improving Compiler Heuristics with Machine Learning
  • http://groups.csail.mit.edu/cag/metaopt/
  • 一言で言うと「遺伝的プログラミングで最適化器を作る」
  • 二言で言ってもそうなのだけど、なにかある優先度関数に基づいて動作を決める最適化（例：レジスタ割り当て："要らなそう"な変数からスタックに追い出す）で、その優先度関数をGPで学習させる。パラメタセットはコンパイラ製作者が決めて式をGPが覚える。

.