小型デバイス上でのデータ処理アルゴリズムの使用メモリ領域の効率化

小型设备上数据处理算法的高效内存使用

• 批准号: 19K11820
• 负责人: 山上 智幸
• 金额: $ 2.75万
• 依托单位: University of Fukui
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19K11820/
• 关键词: 線型領域仮説; 弱線型メモリ領域; 一様性有限オートマトン族; 滝型論理回路; コルモゴロフ計算量; 並列計算; 情報の論理的な深さ; データマイニング; 機械学習; 量子コンピュータ; プッシュダウンオートマトン; ファジー技術; 線形領域仮説; 弱線形メモリ領域; 多項式時間アルゴリズム; シンクロナイゼーション; NL完全問題; オートマトン; メモリ領域; 線形メモリ領域量仮説; 多項式時間; 量子アニーリング; パラメタ付き決定問題; 線形メモリ領域

2022年度は7つの査読付き国際会議論文が採択され Springer 社から出版された。その他に、2つの査読付き論文が Elsevier 社の専門雑誌に掲載された。これらの論文で得られた研究成果の幾つかを簡単に記述する。対数領域計算量小型デバイスの数学的計算モデルを使い、デバイスの計算能力の分析を行った。こうした計算モデルの中でも特に、1970年代後半に提案された多項式状態数を持つ非一様性有限オートマトンの無限族モデル上の非決定性計算に着目し、初期状態から受理状態へ続く計算路が満たす条件の種類による計算量クラス間の新たな関係性を示すことで、相対的な計算能力を示した。2021年に発表した、書き換え回数制限のあるメモリ専用の保管テープを有する、決定性オートマトンを非決定性に拡張した計算モデルを今回新たに導入した。更に滝型論理回路と呼ぶ論理回路を定義し、前述の非決定性オートマトンとの同等性を証明し、国際会議で口頭発表を行った。国際会議論文は後日 Springer 社より出版された。「線形領域仮説」は、2017年に本研究者が提案した仮説で有り、2SAT3と呼ばれる充足可能な条件付き論理式の集合を多項式時間で認識するには、弱線形領域量では不十分であることを主張する。仮説の提案以降、既に5つの論文が出版されていて、その中の2つは2022年度中に国際会議で発表し、Springer社から論文が出版されている。その一つでは、2SAT3と同等の計算量を有する3つの新たな問題を提案し、2017年に導入された「短い還元性」の概念を用いて計算の複雑さの同等性を証明した。もう一つでは、細粒化時間計算量の研究の発展を模範として新たに細粒化領域量の概念を導入し、線形領域仮説の下で幾つかの決定問題の計算不可能性を証明した。

施普林格（Springer）在2022年通过并发表了七篇由同行评审的国际会议论文。简要描述了从这些论文中获得的一些研究结果。对数域计算复杂设备的数学计算模型用于分析设备的计算能力。在这些计算模型中，我们专注于非确定的计算，对1970年代后期提出的多项式状态的非均匀有限自动机模型进行了无限的家族模型，并在计算复杂类中提出了新的关系，基于计算路径的类型，该计算路径的类型从初始状态到接受状态持续到接受状态，表明相对计算能力满足，这表明了相对计算能力。现在，我们引入了一种新的计算模型，该模型将确定性自动机扩展到了非确定性，该模型于2021年宣布，其存储胶带专用于记忆，其重写数量有限。此外，定义了一个名为“瀑布型逻辑电路”的逻辑电路，并证明了它与上述非确定自动机的等效性，并在国际会议上进行了口头介绍。施普林格以后发表了国际会议讨论。 “线性区域假设”是研究人员在2017年提出的假设，并认为弱线性区域数量不足以识别一组在多项式时间内称为2SAT3的令人满意的条件逻辑表达式。自提出假设以来，已经发表了五篇论文，其中两篇论文将在2022财政年度在国际会议上发表，施普林格已经发表了一篇论文。在其中一个中，我们提出了相当于2SAT3的计算复杂性的三个新问题，并使用2017年引入的“简化缩减”概念证明了计算复杂性。另一个例子是，使用对精细元素时间计算的研究进行精细元素面积量的概念，并证明在某些决策性问题下，在局部性问题下进行了一些决策性问题。

项目成果

書き換え制限付き決定性オートマトンと繰り返し補題

具有有限重写和迭代引理的确定性自动机

• 发表时间: 2019
• 作者: Tomoyuki Yamakami;Eitatsu Mikami;Tomoyuki Yamakami;三神栄達・山上智幸;吉田光星・山上智幸
• 通讯作者: 吉田光星・山上智幸

Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers

单向量子有限状态传感器流数据的量子逻辑深度和浅度

• 发表时间: 2021
• 作者: Henning Fernau;Petra Wolf;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami
• 通讯作者: Tomoyuki Yamakami

Expressing Power of Elementary Quantum Recursion Schemes for Quantum Logarithmic-Time Computability

表达量子对数时间可计算性的基本量子递归方案的能力

• DOI: 10.1007/978-3-031-15298-6_6
• 发表时间: 2022
• 期刊: Proceedings of the 28th International Workshop on Logic, Language, Information, and Computation, Lecture Notes in Computer Science
• 作者: Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami
• 通讯作者: Tomoyuki Yamakami

How does adiabatic quantum computation fit into quantum automata theory?

绝热量子计算如何适应量子自动机理论？

• DOI: 10.1007/978-3-030-23247-4_22
• 发表时间: 2019
• 期刊: Proceedings of the 21st IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science
• 作者: Henning Fernau;Petra Wolf;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami
• 通讯作者: Tomoyuki Yamakami

A Schematic Definition of quantum Polynomial Time Computability

量子多项式时间可计算性的示意性定义

• DOI: 10.1017/jsl.2020.45
• 发表时间: 2020
• 期刊: The Journal of Symbolic Logic
• 作者: Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami and Eitatsu Mikami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami
• 通讯作者: Tomoyuki Yamakami