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。我们在婴儿车上设计了有效的平行算法。该算法使用（MN/LOG N）处理器在O（log n）时间内运行，其中M和N分别是输入模式和文本的大小。3。我们调查了Trs.4中最外在重写策略的实现方法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。