論理回路族の階層性の証明と論理合成CADシステムの評価への応用

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

本研究の目的は,計算量クラスの階層構造を解明し,論理合成システムの評価に応用できる定理を得ることである.平成14年度は,主として下記の3つの結果を得た.1.並列計算機モデルの最も基本的なものとして,セルオートマトン(Cellular Automaton, CA)がある.双曲空間で定義したCAの能力は,計算時間を増やせば真に上昇するという「双曲CAの時間計算量の階層定理」を得た.本定理は,ポーランドで開催された国際The 27th International Symposium on Mathematical Foundations of Computer Science)にて研究成果を公表した.また,一次元決定性CAについても,同様の時間計算量の階層定理が得られた.一次元決定性CAに関する階層定理は,国際学術雑誌(Theoretical Computer Science)に採録されている.2.時間計算量を小さくする方法の一つに処理の並列化がある.イテラティブアレイ(Iterative Array)と呼ばれる計算機モデルは,処理の並列化によって時間計算量を二次関数的に減少させることができるという「計算量の加速定理」を得た.本結果は,国際学術雑誌(Acta Informatica)に採択されている.3.保存的な性質をもつ2次元空間内で,論理万能という高い能力をもつ計算機モデルが設計可能であることを示した.本結果は,国際会議(The 3rd International Conference on Unconventional Models of Computation)にて公表した.