权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

使用正则语言进行逻辑函数的计算复杂度分析

基本信息

批准号：
08640307
负责人：
戸田誠之助
金额：
$ 1.02万
依托单位：
Nihon University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1996
资助国家：
日本
起止时间：
1996 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08640307/
关键词：
計算量理論オートマトン理論論理関数群モノイド正則言語

项目摘要

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

The basic computation scale of the group logic circuit is "the number of segments" and the upper action of the 5-th symmetric group is non-deterministic finite. In addition,NUDFA has a finite number of generalizations to calculate the structure of logical circuits. The theory of algebra is the result of the analysis of logic circuits. NUDFA has been studying for 10 years, and there are many unsolved problems. In this study, the logical relations are calculated, which means that the structure of the universal group is investigated. As a result, NUDFA calculates any logical relationship between the non-zero group and M. Second, any logical relation f is equal to f. The length of f is equal to f.