Synthetic Research on the Theory of Algorithms

算法理论综合研究

• 批准号: 06302013
• 负责人: KOBAYASHI Kojiro
• 金额: $ 4.99万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (A)
• 财政年份: 1994
• 资助国家: 日本
• 起止时间: 1994 至 1996
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-06302013/
• 关键词: Identification of Differential Equations; Knowledge Propositional Logic; Algebraic Semantics; Relational Algebra; Verification of Programs; Temporal Logic; Structure of Proteins; Music Information Processing; 高階単一化; セルオートマトン; 文字列パターン; 様相論理; 時間

1. Theory of Algorithms : A framework for developing a theory of numerical computation based on the theory of algorithms was proposed. A method to identify a differential equation from observed numerical data of behavior of a physical system obeying the equation was shown. This method corrects the weakness of the usual one concerning the increase of sizes of intervals resulting from division. 2. Logic and Algorithms : A normal form theorem for the knowledge propositional logic was obtained. Some results that show the usefulness and the limitation of algebraic semantics for nonclassical propositional logic were obtained. The relational calculus and the relational algebra have been sncessfully applied to formulate and analyze several basic notions in computer science such as nondeterministic processes, knowledge base systems, graph rewriting systems, and so on. 3. Programming Languages and Models of Computation : Several formal systmes for analyzing the behavior of parallel programs have been proposed. In one of them, the envelope theory, we can analyze the behavior of parallel programs more naturally than in the usual temporal logic. 4. Algorithms and their Complexity : A new tree structure for representing systax of sentences has been proposed and an English to Japanese translation system based on this tree structure was developed. One method for visualizing music expression in an object oriented environment has been proposed. A hypergraph representation of structures of proteins that captures their tertiary structures in loose way has been proposed. Using this representaion, conformation rules can be formulated as graph rewriting rules, and a PAC learning algorithm has been discovered for a class of conformations. It has been shown that the class of edge-magic graphs cannot be characterized with inhibiting subgraphs.

1.算法理论：提出了一个基于算法理论发展数值计算理论的框架。给出了一种从服从微分方程的物理系统行为的观测数值数据中识别微分方程的方法。这种方法纠正了通常方法中由于除法而使区间增大的缺点。2.逻辑与算法：给出了知识命题逻辑的范式定理。得到了一些结果，说明了代数语义对非经典命题逻辑的有用性和局限性。关系演算和关系代数被广泛地应用于计算机科学中的一些基本概念，如不确定过程、知识库系统、图重写系统等。编程语言和计算模型：已经提出了几种分析并行程序行为的形式系统。其中之一，包络理论，我们可以分析的行为，并行程序比通常的时间逻辑更自然。4.算法及其复杂性：提出了一种新的表示句子系统的树结构，并开发了一个基于该树结构的英日翻译系统。已经提出了一种用于在面向对象的环境中可视化音乐表达的方法。提出了一种蛋白质结构的超图表示方法，它以松散的方式捕捉蛋白质的三级结构。利用这种表示，构象规则可以表示为图重写规则，并为一类构象发现了PAC学习算法。证明了边幻图类不能用抑制子图来刻画。

项目成果

H.Enomoto: "The condition of Beineke and Harary on edge-disjoint paths some of which are openly disjoint" Tokyo J.Math.17. 355-357 (1994)

H.Enomoto：“Beineke 和 Harary 在边不相交路径上的条件，其中一些路径是公开不相交的”Tokyo J.Math.17。

M.Sato: "Intuitionistic and classical natural deduction systems with the Catch and Throw rules" Theoretical Computer Science. (to appear).

M.Sato：“具有捕捉和投掷规则的直觉和经典自然演绎系统”理论计算机科学。

R.Beals: "On the complexity of negation-limited Boolean networks" SIAM J.Computing. (to appear).

R.Beals：“论负限制布尔网络的复杂性”SIAM J.Computing。

M.Takahashi: "Normal proofs and their grammar" Information and Computation. 125. 144-153 (1996)

M.Takahashi：“正规证明及其语法”信息与计算。

有川節夫: "形式言語の理論" 丸善出版(to appear),

有川节夫：《形式语言理论》丸善出版社（待出），