Synthetic Research on the Theory of Algorithms

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

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.