近似法に基づく論理関数の複雑さの評価に関する研究

基于近似方法评价逻辑函数复杂度的研究

基本信息

批准号：
11780182
负责人：
天野一幸
金额：
$ 1.34万
依托单位：
Tohoku University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1999
资助国家：
日本
起止时间：
1999 至 2000
项目状态：
已结题

项目摘要

本研究は,与えられた論理関数を計算する最小の論理回路のサイズに対する下界を導出する手法を開発することを目標とするものである.本研究では特に,この問題に対する有望な手法として知られる近似法を,従来は単調論理回路,すなわち,論理和ゲートと論理積ゲートのみからなる論理回路に対してのみ適用可能であったものから,一般の論理回路モデルや,更には決定木モデルにおいても適用可能となるように拡張することに主眼をおき研究を行った.本年度の研究において得られた主な結果は以下のとおりである.1.ゲートの出力値が,そのゲートの入力の和のある定数剰余によってのみ定まる,いわゆる剰余回路モデルにおいて,任意のサイズの定数段剰余回路は,2段の等価な剰余回路に変換可能であることを代数的手法を用いて示した.また,その出力値が入力変数のうち値1をとるものの個数で定まる関数である対称関数について,これを計算する2段の剰余回路に対する必要条件を,フーリエ変換的手法を用いて示した.また,これら2つの結果と近似法を組み合わせて,対称関数を計算する剰余回路のサイズの下界を導いた.2.並列計算のモデルとして,近年盛んに研究が行われている併置決定木群を用いた計算量について解析を行った.種々の論理関数の近似度,すなわち,与えられた論理関数をある限定された関数クラスに属する関数のみを用いて近似する場合の,近似の度合いの限界値について解析することを通して,併置決定木群の計算量に関する未解決問題のいくつかに対する回答を与えた.

这项研究的目标是开发一种计算给定逻辑函数的最小逻辑电路尺寸下限的方法，以前，近似方法只能应用于单调逻辑电路，即仅由组成的逻辑电路。或门和与门，到通用逻辑电路模型。今年的研究取得的主要成果如下： 1. 门的输出在所谓的余数电路模型中，其值仅由其门的输入之和的常数余数决定，常数-任何规模的级余数电路都可以转换为等效的两级余数电路。我们使用代数方法展示了这一点。我们还展示了两级余数电路计算对称函数的必要条件，该函数的输出值由取值为 1 的输入变量的数量确定。，使用傅立叶变换方法。另外，通过结合这两个结果和近似方法，我们得出了计算对称函数的余数电路的大小的下界。 2.并行计算模型。我们使用近年来积极研究的并置决策树来分析计算复杂度，通过分析仅使用函数逼近时的逼近度极限值，我们为有关并置计算复杂性的一些未解决的问题提供了答案。决策树。

项目成果

期刊论文数量（10）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Kazuyuki Amano: "On the Negation-Limited Circuit Complexity of Merging"Lecture Notes in Computer Science. 1627. 204-209 (1999)

Kazuyuki Amano：“论合并的负限制电路复杂性”计算机科学讲义。

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

天野一幸: "モノポリストゲームのゲーム長(手数)について"電子情報通信学会技術研究報告 -コンピュテーション-. 2000・11. 41-48 (2000)

天野一之：“关于垄断游戏的游戏长度（步数）”IEICE技术研究报告-计算- 41-48（2000）。

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

天野一幸: "決定不における補助ビット問題について"電子情報通信学会技術研究報告 -コンピュテーション-. 2000・10. 57-64 (2000)

Kazuyuki Amano：“关于未定情况下的辅助位问题”IEICE技术研究报告-计算-2000・10.57-64（2000）。

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

Kazoyoki Amano: "On the Negation-Limited Circuit Complexity of Merging"Discrete Applied Mathematics. (発表予定). (2001)

Kazoyoki Amano：“论合并的负限制电路复杂性”离散应用数学（即将发表）。

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

天野一幸: "ブール関数のフーリエ変換とその応用"電子情報通信学会誌. 82巻12号. 1270-1272 (1999)

Kazuyuki Amano：“布尔函数的傅立叶变换及其应用”，电子信息通信工程师学会杂志，第 82 卷，第 12 期。1270-1272 (1999)。

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

天野一幸其他文献

論理関数のPTF表現のXOR補題について

关于逻辑函数PTF表示的XOR引理

DOI：
发表时间：
2016
期刊：
影响因子：
0
作者：
Kazuyuki Amano;Shin-ichi Nakano;木村健斗，天野一幸;吉田　昌史，天野　一幸;Kazuyuki Amano;Kazuyuki Amano;Kazuyuki Amano and Yoshinobu Haruyama;天野一幸;天野一幸，舘将馬
通讯作者：
天野一幸，舘将馬

凹凸のあるピースにおけるアンチスライドパズルの解析

不平整块的防滑拼图分析

DOI：
发表时间：
2019
期刊：
影响因子：
0
作者：
木村健斗;天野一幸
通讯作者：
天野一幸

しきい値回路のパターン数について

关于阈值电路模式的数量

DOI：
发表时间：
2008
期刊：
影响因子：
0
作者：
Kei Uchizawa;Kazuyuki Amano;Hideaki Fukuhara;澤田清;瀧本英二;Shigeaki Harada;Shigeaki Harada;酒井義文;天野一幸;Kazuyuki Amano;Takayuki Sato;内沢啓;Kazuyuki Amano;Shigeaki Harada;Tatsuya Watanabe;酒井義文;Nobuyoshi Sato;Kazuyuki Amano;Kazuyuki Amano;原田薫明;Kazuyuki Amano;Eiji Takimoto;Nobuyoshi Sato;Nobuyoshi Sato;Kazuyuki Amano;川端新伍;瀧本英二;内沢啓
通讯作者：
内沢啓

ブール関数に対するフィルタのノイズ除去効果について

关于滤波器对布尔函数的去噪效果

DOI：
发表时间：
2007
期刊：
影响因子：
0
作者：
Kei Uchizawa;Kazuyuki Amano;Hideaki Fukuhara;澤田清;瀧本英二;Shigeaki Harada;Shigeaki Harada;酒井義文;天野一幸;Kazuyuki Amano;Takayuki Sato;内沢啓;Kazuyuki Amano;Shigeaki Harada;Tatsuya Watanabe;酒井義文;Nobuyoshi Sato;Kazuyuki Amano;Kazuyuki Amano;原田薫明;Kazuyuki Amano;Eiji Takimoto;Nobuyoshi Sato;Nobuyoshi Sato;Kazuyuki Amano;川端新伍;瀧本英二;内沢啓;Kazyuki Amano;Kazuyuki Amano;酒井義文;天野一幸;唐崎正史
通讯作者：
唐崎正史

記号毎に全順序付けられた有向非循環グラフのトポロジカルソート配列と配列の最長共通部分配列アルゴリズム

对每个符号完全排序的有向无环图的拓扑排序数组和数组的最长公共子序列算法

DOI：
发表时间：
2007
期刊：
影响因子：
0
作者：
Kei Uchizawa;Kazuyuki Amano;Hideaki Fukuhara;澤田清;瀧本英二;Shigeaki Harada;Shigeaki Harada;酒井義文;天野一幸;Kazuyuki Amano;Takayuki Sato;内沢啓;Kazuyuki Amano;Shigeaki Harada;Tatsuya Watanabe;酒井義文;Nobuyoshi Sato;Kazuyuki Amano;Kazuyuki Amano;原田薫明;Kazuyuki Amano;Eiji Takimoto;Nobuyoshi Sato;Nobuyoshi Sato;Kazuyuki Amano;川端新伍;瀧本英二;内沢啓;Kazyuki Amano;Kazuyuki Amano;酒井義文
通讯作者：
酒井義文