Name
Abstract | ||
|---|---|---|
A simple method is proposed for testing equivalence in a restricted domain of two given term rewriting systems. By using the Church-Rosser property and the teachability of term rewriting systems, the method allows us to prove equivalence of these systems without the explicit use of induction; this proof usually requires some kind of induction. The method proposed is a general extension of inductionless induction methods developed by Musser, Goguen, Huet and HuUot, and allows us to extend inductionless induetior~ concepts to not only term rewriting systems with the termination property, but also various reduction systems: term rewriting systems without the termination property, string rewriting systems, graph rewriting systems, combinatory reduction systems, and resolution systems. This method is applied to test equivalence of term rewriting systems, to prove the inductive theorems, and to derive a new term rewriting system from a given system by using equivalence transformation rules. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1016/0304-3975(91)90004-L | Theor. Comput. Sci. |
Keywords | Field | DocType |
term rewriting systems,prove equivalence,graph rewriting | Discrete mathematics,Semi-Thue system,Computer science,Algorithm,Reachability,Equivalence (measure theory),Rewriting,Confluence,Graph rewriting,Knuth–Bendix completion algorithm | Journal |
Volume | Issue | ISSN |
90 | 2 | 0304-3975 |
ISBN | Citations | PageRank |
0-387-16780-3 | 9 | 0.79 |
References | Authors | |
13 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yoshihito Toyama | 1 | 533 | 49.60 |