A critical pair arises in a
term rewriting system
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or redu ...
when two rewrite rules overlap to yield two different terms. In more detail, (''t''
1, ''t''
2) is a critical pair if there is a term ''t'' for which two different applications of a rewrite rule (either the same rule applied differently, or two different rules) yield the terms ''t''
1 and ''t''
2.
Definitions
The actual definition of a critical pair is slightly more involved as it excludes pairs that can be obtained from critical pairs by substitution and orients the pair based on the overlap. Specifically, for a pair of overlapping rules
and
, with the overlap being that