覆面算を列挙するオートマトンの効率的な構築手法
コンピュテーション研究会 (COMP研),
信学技報 Vol.120, pp.16-23
(2020)
開催日:
2020年12月4-4日
開催地: オンライン
Abstract / 概要
覆面算とは記号による算術式が与えられ，その式を成立させるような記号から数字への対応方法を探す数学パズルである．2018年にNozakiらはk進数において可解な覆面算のDFAを用いた列挙手法を提案し，これを用いて覆面算に関する様々な解析を行なった．この覆面算DFA構築においてはkを大きくしていくとそのサイズが急激に増加するという問題があり，この計算爆発をいかに抑えるか，というのが課題となっている．本発表ではNozakiらが残した課題を解決し，効率的に覆面算を列挙するDFAを構築する手法を提案する．