Foundamental Study on Fundational Model of Concurrent Computation

并发计算基本模型的基础研究

基本信息

批准号：
02680020
负责人：
SAKABE Toshiki
金额：
$ 1.09万
依托单位：
Nagoya University
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1990
资助国家：
日本
起止时间：
1990 至 1991
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-02680020/
关键词：
concurrent computation Functional computation model CCS broadcast narrowing concurrent process term rewriting system dynamic term rewriting calculas 並行プロセス動的項書換論理型計算モデル同期通信

项目摘要

The purpose of this research project is to develop a functional model of concurrent computation based on narrowing such that we can analyze and verify concurrent programs by using rewriting techniques.The results we obtained in the research project are as follows.We first proposed a computation model called Dynamic Term Rewriting Calculus (DTRC, for short). It is a preliminary version of our target model. DTRC has features such as dynamically changing rewrite rules during computation and hierarchically declaring function symbols, variables and rewrite rules. We obtained fundamental results on confluency and termination of DTRC terms.We also investigated the theory of process algebras and proposed two extensions of CCS. One is CCS with limit values. It has term rewriting systems as the mechanism for defining (possibly limit) values and has the feature of branching by a limit value. We gave a semantics for the extended CCS by introducing a new concept of test precision. The other extension is CCS with broadcast (called CCS+b). It formalizes broadcast which is characterized with one-to-many communication and nondeterministic communication in receiving signals. We obtained commutativity and associativity lows for choice and parallel composition operators, and expansion low. These lows are useful for analyzing processes.We studied tree pattern matching and found a parallel algorithm for tree pattern matching which improved the algorithm of Ramesh et al. in time and space.

该研究项目的目的是开发基于狭窄的并发计算的功能模型，以便我们可以使用重写技术来分析和验证并发程序。我们在研究项目中获得的结果如下。我们首先提出了一个称为动态术语重写计算的计算模型（简称DTRC）。这是我们目标模型的初步版本。 DTRC具有在计算过程中动态更改重写规则的功能，以及层次声明的函数符号，变量和重写规则。我们获得了DTRC术语汇合和终止的基本结果。我们还研究了过程代数理论，并提出了两种CCS的扩展。一个是具有极限值的CC。它具有术语重写系统作为定义（可能限制）值的机制，并具有分支的特征，分支为限值。我们通过引入一个新的测试精度概念为扩展的CC提供了语义。另一个扩展名是带有广播的CC（称为CCS+B）。它正式的广播以一对多的通信和无确定性的通信为特征。我们获得了选择和平行组成算子的换向性和关联性低，并且膨胀低。这些低点对于分析过程很有用。我们研究了树模式匹配，并找到了针对树模式匹配的平行算法，该算法改善了Ramesh等人的算法。在时空。