表題番号:2015K-107 日付:2016/02/19
研究課題反応オートマトンによる化学反応の構成的解析
研究者所属(当時) 資格 氏名
(代表者) 教育・総合科学学術院 教育学部 教授 横森 貴
研究成果概要

FAMMの研究目的は,「メモリとして多重集合のみを許される有限オートマトンの計算能力を解析する」ことである.この研究テーマに関する予想として「多重集合というが概念が情報を保持するデータ構造として極めてシンプルである(すなわち,記号列のような記号の順序情報が保持できない)ことから,FAMMの計算能力は限られている」と思われていた.研究の結果,FAMMという形式的枠組みにを用いて,従来から研究が行われている計算モデルであるチューリング機械を中核とするオートマトン理論を再構築することができた.これらの結果は,多重集合による計算/情報処理能力を解明する新しい知見を与えている.