正則言語による論理関数の計算量解析

点击翻译按钮获取中文摘要

組み合わせ論理回路の基本的な計算量尺度である「段数」と5次対称群の上で動作する非一様決定性有限オートマトン(以下,NUDFAと略す)の基本的な計算量尺度である「長さ」とが密接な関係にあることが示されて以来,様々な群やモノイドの上で動作するNUDFAと組み合わせ論理回路のクラスとの関係が調べられている.また更に,NUDFAが有限オートマトンを一般化した計算モデルであることから,幾つかの組み合わせ論理回路のクラスの計算構造が正則言語によって表現され分析され得ることが知られている.このことは,代数的オートマトン理論における既知の結果が論理回路のクラスを分析するための道具になり得ることを示唆している.しかしながら,NUDFAに関わる研究が始まってまだ10年程度しか経過していんこともあり,多くの素朴な疑問が未解決のまま残されている状況にある.本研究では,まず,あらゆる論理関数を計算できるという意味で万能な群やモノイドの構造について考察した.この結果,非ベキ零群を埋蔵した任意のモノイドMに対して,Mの上で動作するNUDFAが任意の論理関数を計算できることを示した.次に,任意の論理関数fに対して,fを計算する5次対称群ので動作するNUDFAの長さがfを表す最も短い論理式の長さの二乗程度であることが知られているが,この関係が任意の非可解群に関して成立することを示した.