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.