fixedpoint.jp


"R.E. Axiomatization of Conditional Independence"の紹介 (2014-03-05)

命題論理 で表現できる条件付き独立性recursively enumerable な論理式の集合で公理化できるという論文です: http://arxiv.org/abs/1310.6430

既にこの理論が undecidable であることが分かっているので、期待しうる次善の結果ということになります。説明されている公理のうち diagram で表現される式は一見複雑に見えますが、別にもっとうまい公理化があるのかもしれません。

この成果は、例えばマインスイーパ数独といったパズルにおいて、見えている情報のみから「勘に頼らずに」正答を順に埋めていくことができるかどうかを判定するのに応用できると考えられます。


© 2006-2023 fixedpoint.jp