Title | ||
---|---|---|
Finding Canonical Rewriting Systems Equivalent to a Finite Set of Ground Equations in Polynomial Time |
Abstract | ||
---|---|---|
In this paper, it is shown that there is an algorithm which, given any finite set E of ground equations, produces a reduced canonical rewriting system R equivalent to E in polynomial time. This algorithm based on congruence closure performs simplification steps guided by a total simplification ordering on ground terms, and it runs in time O(n
3). |
Year | DOI | Venue |
---|---|---|
1988 | 10.1007/BFb0012832 | CADE |
Keywords | Field | DocType |
ground equations,finding canonical rewriting systems,polynomial time,finite set | Discrete mathematics,Characteristic polynomial,Stable polynomial,Finite set,Polynomial,Monic polynomial,Rewriting,Wilkinson's polynomial,Matrix polynomial,Mathematics | Conference |
ISBN | Citations | PageRank |
3-540-19343-X | 16 | 1.68 |
References | Authors | |
10 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jean H. Gallier | 1 | 749 | 111.86 |
Paliath Narendran | 2 | 1100 | 114.99 |
David A. Plaisted | 3 | 1680 | 255.36 |
Stan Raatz | 4 | 176 | 37.68 |
Wayne Snyder | 5 | 225 | 23.79 |