权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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.

本研究项目的目的是开发一种基于窄化的并发计算功能模型，以便我们可以使用重写技术来分析和验证并发程序。我们在研究项目中获得的结果如下。我们首先提出了一种称为动态项重写演算（Dynamic Term Rewriting Calculus，简称DTRC）的计算模型。这是我们目标模型的初步版本。 DTRC具有计算过程中动态改变重写规则以及分层声明函数符号、变量和重写规则等特点。我们在DTRC项的汇合和终止方面获得了基本结果。我们还研究了过程代数理论并提出了CCS的两个扩展。一种是具有极限值的 CCS。它具有术语重写系统作为定义（可能是极限）值的机制，并且具有按极限值分支的特征。我们通过引入测试精度的新概念给出了扩展CCS的语义。另一个扩展是带广播的CCS（称为CCS+b）。它将广播形式化，广播的特点是一对多通信和接收信号的非确定性通信。我们获得了选择运算符和并行组合运算符的交换性和结合性低值以及扩展性低值。这些低点对于分析过程很有用。我们研究了树模式匹配，发现了一种树模式匹配的并行算法，该算法改进了 Ramesh 等人的算法。在时间和空间上。