対数領域計算モデルのメモリアクセス回数による能力の比較
基于内存访问次数的对数域计算模型能力比较
基本信息
- 批准号:20K19741
- 负责人:
- 金额:$ 2.16万
- 依托单位:
- 依托单位国家:日本
- 项目类别:Grant-in-Aid for Early-Career Scientists
- 财政年份:2020
- 资助国家:日本
- 起止时间:2020-04-01 至 2024-03-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
本研究の目的は分岐プログラムの下界解析の手法を確立する事である.そのために幅制限分岐プログラムが表現する論理関数に対する解析を行った.計算量理論では計算モデルに対する充足性問題を解くアルゴリズムの上界解析の手法が同計算モデルのサイズ下界の手法に応用される例が多く研究されており,本研究でも同様に幅に制限をもつ分岐プログラムに対する充足性問題を解くアルゴリズムの研究を進めている.その結果,一般的な論理関数の充足性問題に解空間の制限を付随させたSub-SATと呼ばれる問題を効率的に解くアルゴリズムを構築した.本結果を用いることで幅制限を持つ分岐プログラムを対象にした充足性問題に対しても高速に解を求めることができるようになり,これを応用させることで幅制限を持つ分岐プログラムに対しての下界解析の手法を構築できないかと模索している.本研究の期間は三年であり,三年目を終えた時点で分岐プログラムを入力とする充足可能性問題に対して三つの国際論文誌を出版することができ,多くの知見をえることができた.しかしながら,これらの成果は本研究の主目的であるメモリアクセス回数とは異なる制限に対する結果である.分岐プログラムという対数領域計算モデルが本質的にどういった性質のものなのかを解明するという点では前進しているが,これらの知見を応用させることで下界解析の手法を新たに構築するという点では課題が残っている状況である.分岐プログラムの一回読み制限や幅制限ををさらに緩和したモデルに対する下界解析の研究成果は世界でもまだ存在していない.その最初の一歩を踏み出すために分岐プログラムの様々な特徴について研究を進めている.本研究実績はその結果であると言える.
The purpose of this study is to establish a method for analyzing the lower bound of the bifurcation. The analysis of the logical relationship between the amplitude limit and the difference between the amplitude limit and the difference between the amplitude limit. Computational quantity theory is used to solve the problem of sufficiency of the computational domain. The method of upper bound analysis and the method of lower bound analysis of the computational domain are used to study the problem of sufficiency of the computational domain. As a result, the adequacy problem of general logic relations is constructed by the constraint of solution space and the problem of efficiency. The results show that the amplitude limit is used to construct the lower bound analysis method for the problem of sufficiency of the object. The period of this study is three years. At the end of the three years, there are differences in the power of the study. There are sufficient possibilities for the publication of international papers. The results of this study are contrary to the main purpose of this study. Divergent domain calculation, essential domain, property, solution, advance domain, knowledge domain, application domain, lower domain analysis domain, new domain construction domain, residual domain. The results of the study on the lower bound analysis of the differential equation are available in the world. The first step is to divide and divide the population into groups and study the characteristics. This research achievement is opposite the result
项目成果
期刊论文数量(2)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
A Satisfiability Algorithm for Deterministic Width-2 Branching Programs
确定性宽度2分支程序的可满足性算法
- DOI:10.1587/transfun.2021eap1120
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Tomu MAKITA;Atsuki NAGAO;Tatsuki OKADA;Kazuhisa SETO;Junichi TERUYAMA
- 通讯作者:Junichi TERUYAMA
Satisfiability Algorithm for Syntactic Read-k-times Branching Programs
语法读取k次分支程序的可满足性算法
- DOI:10.1007/s00224-020-09996-3
- 发表时间:2020
- 期刊:
- 影响因子:0.5
- 作者:Atsuki Nagao;Kazuhisa Seto;and Junichi Teruyama
- 通讯作者:and Junichi Teruyama
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
長尾 篤樹其他文献
長尾 篤樹的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('長尾 篤樹', 18)}}的其他基金
Exploring the Function to Show the Limit of Log-space Computation Models
探索显示对数空间计算模型极限的函数
- 批准号:
23K10981 - 财政年份:2023
- 资助金额:
$ 2.16万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
対数領域計算モデルの計算限界の解明
阐明对数域计算模型的计算极限
- 批准号:
14J04867 - 财政年份:2014
- 资助金额:
$ 2.16万 - 项目类别:
Grant-in-Aid for JSPS Fellows
相似海外基金
グラフデータにおける問合せ式充足可能性問題の計算複雑さおよび判定アルゴリズム
图数据查询可满足性问题的计算复杂度与决策算法
- 批准号:
21K11900 - 财政年份:2021
- 资助金额:
$ 2.16万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
SAT(充足可能性)問題の並列局所探索アルゴリズムの研究と超並列計算機への実装
SAT(可满足性)问题的并行局部搜索算法研究及其在大规模并行计算机上的实现
- 批准号:
11F01807 - 财政年份:2011
- 资助金额:
$ 2.16万 - 项目类别:
Grant-in-Aid for JSPS Fellows
SAT(命題論理の充足可能性)問題を解くアルゴリズムに関する研究
解决SAT(命题逻辑可满足性)问题的算法研究
- 批准号:
17700135 - 财政年份:2005
- 资助金额:
$ 2.16万 - 项目类别:
Grant-in-Aid for Young Scientists (B)