A Study of Term Matching in the Equational Language Processor

等式语言处理器中术语匹配的研究

• 批准号: 01550282
• 负责人: HIRATA Tomio
• 金额: $ 0.9万
• 依托单位: Nagoya University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1989
• 资助国家: 日本
• 起止时间: 1989 至 1990
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-01550282/
• 关键词: Equational language; Term matching; Tree pattern matching

The purpose of this research is to develop algorithms and data structure for efficient term matching and rewriting. The results obtained are as follows.1. We propose three algorithms for tree-pattern matching. By preprocessing the pattern, the first one performs efficient matching. The second one is very efficient when the pattern contains few variables. The last one is a parallel algorithm based on a systolic array.2. We design an efficient parallel algorithm on PRAM. The algorithm runs in O (log n) time using (mn/log n) processors, where m and n are sizes of input pattern and text, respectively.3. We investigate implementation methods of the parallel outermost rewriting strategy in TRS.4. We published the above results as a research report.

本研究的目的是开发用于高效术语匹配和重写的算法和数据结构。得到的结果如下： 1．我们提出了三种树模式匹配算法。通过预处理模式，第一个执行有效的匹配。当模式包含很少的变量时，第二种方法非常有效。最后一种是基于脉动阵列的并行算法。2．我们在 PRAM 上设计了一种高效的并行算法。该算法使用 (mn/log n) 个处理器在 O (log n) 时间内运行，其中 m 和 n 分别是输入模式和文本的大小。 3．我们研究了TRS.4中并行最外层重写策略的实现方法。我们将上述结果作为研究报告发表。

项目成果

Takashi SHIMATANI: "An on-line algorithm for computing the transitive closure of a graph" The transactions of the IEICE. Vol. J73-D-I. 705-706 (1990)

Takashi SHIMATANI：“一种用于计算图的传递闭包的在线算法” IEICE 的交易。

Tomio HIRATA: "A systolic algorithm for tree pattern matching" The transactions of the IEICE. Vol. J73-D-I. 366-369 (1990)

Tomio HIRATA：“树模式匹配的脉动算法” IEICE 的交易。

平田富夫: "推移的閉包を求めるアルゴリズムのならし計算量" 電子情報通信学会論文誌. J72-D. 720-725 (1989)

Tomio Hirata：“确定传递闭包的算法的存储复杂性”，电子、信息和通信工程师学会汇刊 J72-725 (1989)。

X.H.Tan: "Reporting intersections of cーoriented polygons" 電子情報通信学会英文論文誌. E73. 1886-1892 (1990)

X.H.Tan：“报告 c 向多边形的交集”电子、信息和通信工程师学会英文期刊 E73（1990）。

山本 晋一郎: "TRSインタプリタの並列最外戦略実現法" 電子情報通信学会研究会技術研究報告. COMP88ー94. (1989)

Shinichiro Yamamoto：“实现TRS解释器并行最外层策略的方法”IEICE COMP88-94。