Введение
Алгоритм завершения Кнута — Бендикса (названный в честь Дональда Кнута и Питера Бендикса) — это полурешающий алгоритм для преобразования набора уравнений (над термами) в систему переписывания термов, обладающую свойством конфлюэнтности. В случае успешного завершения алгоритм эффективно решает задачу о равенстве слов для заданной алгебры. Алгоритм Бюхбергера для вычисления базисов Грёбнера является очень похожим алгоритмом. Хотя он был разработан независимо, его также можно рассматривать как реализацию алгоритма Кнута — Бендикса в теории полиномиальных колец.
The Knuth–Bendix completion algorithm (named after Donald Knuth and Peter Bendix) is a semi decision algorithm for transforming a set of equations (over terms) into a confluent term rewriting system. When the algorithm succeeds, it effectively solves the word problem for the specified algebra. Buchberger's algorithm for computing Gröbner bases is a very similar algorithm. Although developed independently, it may also be seen as the instantiation of Knuth–Bendix algorithm in the theory of polynomial rings.
Введение
Для множества уравнений E его дедуктивное замыкание – это множество всех уравнений, которые могут быть выведены путем применения уравнений из E в любом порядке. Формально, E рассматривается как бинарное отношение, является его замыканием по переписыванию, а – замыканием по эквивалентности. Для множества R правил переписывания его дедуктивное замыкание (∘) – это множество всех уравнений, которые могут быть подтверждены применением правил из R слева направо к обеим сторонам, пока они не станут буквально равны. Формально, R снова рассматривается как бинарное отношение, является его замыканием по переписыванию, – его обратным, а (∘) – композицией отношений их рефлексивных транзитивных замыканий ( и ). Например, если – групповые аксиомы, то цепочка выводов
For a set E of equations, its deductive closure is the set of all equations that can be derived by applying equations from E in any order. Formally, E is considered a binary relation, is its rewrite closure, and is the equivalence closure of For a set R of rewrite rules, its deductive closure ( ∘ ) is the set of all equations that can be confirmed by applying rules from R left to right to both sides until they are literally equal. Formally, R is again viewed as a binary relation, is its rewrite closure, is its converse, and ( ∘ ) is the relation composition of their reflexive transitive closures ( and ). For example, if are the group axioms, the derivation chain
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
показывает, что a−1⋅(a⋅b) b является элементом дедуктивного замыкания E. Если – версия E в виде "правила переписывания", то цепочки производных
For a set E of equations, its deductive closure is the set of all equations that can be derived by applying equations from E in any order. Formally, E is considered a binary relation, is its rewrite closure, and is the equivalence closure of For a set R of rewrite rules, its deductive closure ( ∘ ) is the set of all equations that can be confirmed by applying rules from R left to right to both sides until they are literally equal. Formally, R is again viewed as a binary relation, is its rewrite closure, is its converse, and ( ∘ ) is the relation composition of their reflexive transitive closures ( and ). For example, if are the group axioms, the derivation chain
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
показывают, что (a−1⋅a)⋅b ∘ b является элементом дедуктивного замыкания R. Однако нет способа вывести a−1⋅(a⋅b) ∘ b, подобно вышеуказанному, поскольку применение правила (x⋅y)⋅z → x⋅(y⋅z) справа налево не допускается. Алгоритм Кнута – Бендикса принимает набор уравнений E между термами и порядок редукции (>) на множестве всех термов и пытается построить систему переписывания термов, которая является конфлюэнтной и терминирующей, и имеет такое же дедуктивное замыкание, как и E.
Хотя доказательство следствий из E часто требует человеческой интуиции, доказательство следствий из R этого не требует. Для получения более подробной информации см. Конфлюэнтность (абстрактное переписывание) # Мотивирующие примеры, который приводит пример доказательства из теории групп, выполненного как с использованием E, так и с использованием R.
For a set E of equations, its deductive closure is the set of all equations that can be derived by applying equations from E in any order. Formally, E is considered a binary relation, is its rewrite closure, and is the equivalence closure of For a set R of rewrite rules, its deductive closure ( ∘ ) is the set of all equations that can be confirmed by applying rules from R left to right to both sides until they are literally equal. Formally, R is again viewed as a binary relation, is its rewrite closure, is its converse, and ( ∘ ) is the relation composition of their reflexive transitive closures ( and ). For example, if are the group axioms, the derivation chain
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
Правила
For a set E of equations, its deductive closure is the set of all equations that can be derived by applying equations from E in any order. Formally, E is considered a binary relation, is its rewrite closure, and is the equivalence closure of For a set R of rewrite rules, its deductive closure ( ∘ ) is the set of all equations that can be confirmed by applying rules from R left to right to both sides until they are literally equal. Formally, R is again viewed as a binary relation, is its rewrite closure, is its converse, and ( ∘ ) is the relation composition of their reflexive transitive closures ( and ). For example, if are the group axioms, the derivation chain
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
При заданном наборе уравнений E между термами следующие правила вывода могут быть использованы для преобразования его в эквивалентную конвергентную систему переписывания термов (если это возможно):
Они основаны на заданном пользователем порядке редукции (>) на множестве всех термов; он расширяется до хорошо обоснованного порядка (▻) на множестве правил переписывания путем определения (s → t) ▻ (l → r), если
в порядке включения, или
s и l буквально похожи, и t > r.
For a set E of equations, its deductive closure is the set of all equations that can be derived by applying equations from E in any order. Formally, E is considered a binary relation, is its rewrite closure, and is the equivalence closure of For a set R of rewrite rules, its deductive closure ( ∘ ) is the set of all equations that can be confirmed by applying rules from R left to right to both sides until they are literally equal. Formally, R is again viewed as a binary relation, is its rewrite closure, is its converse, and ( ∘ ) is the relation composition of their reflexive transitive closures ( and ). For example, if are the group axioms, the derivation chain
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
Удалить ‹ E∪{s = s} , R › ⊢ ‹ E , R › Композиция ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › если Упростить ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › если Ориентировать ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › если s > t Схлопнуть ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › если по l → r с условием (s → t) ▻ (l → r) Вывести ‹ E , R › ⊢ ‹ E∪{s = t} , R › если (s,t) является критической парой R
For a set E of equations, its deductive closure is the set of all equations that can be derived by applying equations from E in any order. Formally, E is considered a binary relation, is its rewrite closure, and is the equivalence closure of For a set R of rewrite rules, its deductive closure ( ∘ ) is the set of all equations that can be confirmed by applying rules from R left to right to both sides until they are literally equal. Formally, R is again viewed as a binary relation, is its rewrite closure, is its converse, and ( ∘ ) is the relation composition of their reflexive transitive closures ( and ). For example, if are the group axioms, the derivation chain
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
Пример
For a set E of equations, its deductive closure is the set of all equations that can be derived by applying equations from E in any order. Formally, E is considered a binary relation, is its rewrite closure, and is the equivalence closure of For a set R of rewrite rules, its deductive closure ( ∘ ) is the set of all equations that can be confirmed by applying rules from R left to right to both sides until they are literally equal. Formally, R is again viewed as a binary relation, is its rewrite closure, is its converse, and ( ∘ ) is the relation composition of their reflexive transitive closures ( and ). For example, if are the group axioms, the derivation chain
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
Следующий пример выполнения, полученный из решателя уравнений E, вычисляет завершение (аддитивных) групповых аксиом, как в Knuth, Bendix (1970). Он начинается с трех начальных уравнений для группы (нейтральный элемент 0, обратные элементы, ассоциативность), используя f(X,Y) для X+Y и i(X) для −X. 10 отмеченных звездочкой уравнений, как оказалось, составляют полученную конвергентную систему переписывания. "pm" – сокращение от "парамодуляция", реализующая вывод. Вычисление критических пар является примером парамодуляции для уравнительных единичных клаузул. "rw" – переписывание, реализующее композицию, схлопывание и упрощение. Ориентация уравнений выполняется неявно и не записывается. Nr Lhs Rhs Источник 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
См. также Задача о слове (математика) для другого представления этого примера. Системы переписывания строк в теории групп
For a set E of equations, its deductive closure is the set of all equations that can be derived by applying equations from E in any order. Formally, E is considered a binary relation, is its rewrite closure, and is the equivalence closure of For a set R of rewrite rules, its deductive closure ( ∘ ) is the set of all equations that can be confirmed by applying rules from R left to right to both sides until they are literally equal. Formally, R is again viewed as a binary relation, is its rewrite closure, is its converse, and ( ∘ ) is the relation composition of their reflexive transitive closures ( and ). For example, if are the group axioms, the derivation chain
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
Важным случаем в вычислительной теории групп являются системы переписывания строк, которые могут быть использованы для присвоения канонических меток элементам или смежным классам конечно представленной группы как произведению генераторов. Этот особый случай является предметом внимания данного раздела. Мотивация в теории групп
Лемма о критических парах утверждает, что система переписывания термов локально конфлюэнтна (или слабо конфлюэнтна) тогда и только тогда, когда все ее критические пары сходятся. Кроме того, у нас есть лемма Ньюмана, которая утверждает, что если (абстрактная) система переписывания сильно нормализует и слабо сливается, то система переписывания сливается. Итак, если мы можем добавить правила к системе переписывания термов, чтобы заставить все критические пары сходиться, сохраняя при этом сильное нормализующее свойство, то это заставит полученную систему переписывания быть конфлюэнтной. Рассмотрим конечно представленный моноид, где X – конечное множество генераторов, а R – множество определяющих соотношений на X. Пусть X* – множество всех слов в X (т.е. свободный моноид, порожденный X). Поскольку соотношения R порождают отношение эквивалентности на X*, можно рассматривать элементы M как классы эквивалентности X* по R. Для каждого класса {w1, w2, } желательно выбрать стандартный представитель wk. Этот представитель называется канонической или нормальной формой для каждого слова wk в классе. Если существует вычислимый метод определения для каждого wk его нормальной формы wi, то задача о слове легко решается. Конфлюэнтная система переписывания позволяет сделать именно это. Хотя выбор канонической формы теоретически может быть сделан произвольно, этот подход обычно невычислим. (Учитывайте, что отношение эквивалентности на языке может породить бесконечное число бесконечных классов.) Если язык хорошо упорядочен, то порядок < дает согласованный метод определения минимальных представителей, однако вычисление этих представителей все равно может быть невозможным. В частности, если система переписывания используется для вычисления минимальных представителей, то порядок < должен также иметь свойство:
For a set E of equations, its deductive closure is the set of all equations that can be derived by applying equations from E in any order. Formally, E is considered a binary relation, is its rewrite closure, and is the equivalence closure of For a set R of rewrite rules, its deductive closure ( ∘ ) is the set of all equations that can be confirmed by applying rules from R left to right to both sides until they are literally equal. Formally, R is again viewed as a binary relation, is its rewrite closure, is its converse, and ( ∘ ) is the relation composition of their reflexive transitive closures ( and ). For example, if are the group axioms, the derivation chain
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
A < B → XAY < XBY для всех слов A,B,X,Y
For a set E of equations, its deductive closure is the set of all equations that can be derived by applying equations from E in any order. Formally, E is considered a binary relation, is its rewrite closure, and is the equivalence closure of For a set R of rewrite rules, its deductive closure ( ∘ ) is the set of all equations that can be confirmed by applying rules from R left to right to both sides until they are literally equal. Formally, R is again viewed as a binary relation, is its rewrite closure, is its converse, and ( ∘ ) is the relation composition of their reflexive transitive closures ( and ). For example, if are the group axioms, the derivation chain
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
Это свойство называется трансляционной инвариантностью. Порядок, который является одновременно трансляционно инвариантным и хорошо упорядоченным, называется порядком редукции. Из представления моноида можно определить систему переписывания, заданную соотношениями R. Если A x B находится в R, то либо A < B, в этом случае B → A является правилом в системе переписывания, иначе A > B и A → B. Поскольку < является порядком редукции, данное слово W можно сократить до W > W 1 > > W n, где W n не приводимо по системе переписывания. Однако, в зависимости от правил, применяемых на каждом шаге Wi → Wi+1, можно получить два разных неприводимых сокращения Wn ≠ W'm для W. Однако, если система переписывания, заданная соотношениями, преобразована в конфлюэнтную систему переписывания с помощью алгоритма Кнута – Бендикса, то все сокращения гарантированно приведут к одному и тому же неприводимому слову, а именно к нормальной форме для этого слова. Описание ...
For a set E of equations, its deductive closure is the set of all equations that can be derived by applying equations from E in any order. Formally, E is considered a binary relation, is its rewrite closure, and is the equivalence closure of For a set R of rewrite rules, its deductive closure ( ∘ ) is the set of all equations that can be confirmed by applying rules from R left to right to both sides until they are literally equal. Formally, R is again viewed as a binary relation, is its rewrite closure, is its converse, and ( ∘ ) is the relation composition of their reflexive transitive closures ( and ). For example, if are the group axioms, the derivation chain
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right to left application of the rule (x⋅y)⋅z → x⋅(y⋅z) is not allowed. The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E.
While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible):
They are based on a user given reduction ordering (>) on the set of all terms; it is lifted to a well founded ordering (▻) on the set of rewrite rules by defining (s → t) ▻ (l → r) if
in the encompassment ordering, or
s and l are literally similar and t > r.
Delete ‹ E∪{s = s} , R › ⊢ ‹ E , R › Compose ‹ E , R∪{s → t} › ⊢ ‹ E , R∪{s → u} › if Simplify ‹ E∪{s = t} , R › ⊢ ‹ E∪{s = u} , R › if Orient ‹ E∪{s = t} , R › ⊢ ‹ E , R∪{s → t} › if s > t Collapse ‹ E , R∪{s → t} › ⊢ ‹ E∪{u = t} , R › if by l → r with (s → t) ▻ (l → r) Deduce ‹ E , R › ⊢ ‹ E∪{s = t} , R › if (s,t) is a critical pair of R
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded. Nr Lhs Rhs Source 1: * f(X,0) = X initial("GROUP. lop", at line 9 column 1) 2: * f(X,i(X)) = 0 initial("GROUP. lop", at line 12 column 1) 3: * f(f(X,Y),Z) = f(X,f(Y,Z)) initial("GROUP. lop", at line 15 column 1) 5: f(X,Y) = f(X,f(0,Y)) pm(3,1) 6: f(X,f(Y,i(f(X,Y)))) = 0 pm(2,3) 7: f(0,Y) = f(X,f(i(X),Y)) pm(3,2) 27: f(X,0) = f(0,i(i(X))) pm(7,2) 36: X = f(0,i(i(X))) rw(27,1) 46: f(X,Y) = f(X,i(i(Y))) pm(5,36) 52: * f(0,X) = X rw(36,46) 60: * i(0) = 0 pm(2,52) 63: i(i(X)) = f(0,X) pm(46,52) 64: * f(X,f(i(X),Y)) = Y rw(7,52) 67: * i(i(X)) = X rw(63,52) 74: * f(i(X),X) = 0 pm(2,67) 79: f(0,Y) = f(i(X),f(X,Y)) pm(3,74) 83: * Y = f(i(X),f(X,Y)) rw(79,52) 134: f(i(X),0) = f(Y,i(f(X,Y))) pm(83,6) 151: i(X) = f(Y,i(f(X,Y))) rw(134,1) 165: * f(i(X),i(Y)) = i(f(Y,X)) pm(83,151)
See also Word problem (mathematics) for another presentation of this example. String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section. Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent. Consider a finitely presented monoid where X is a finite set of generators and R is a set of defining relations on X. Let X* be the set of all words in X (i. e. the free monoid generated by X). Since the relations R generate an equivalence relation on X*, one can consider elements of M to be the equivalence classes of X* under R. For each class {w1, w2, } it is desirable to choose a standard representative wk. This representative is called the canonical or normal form for each word wk in the class. If there is a computable method to determine for each wk its normal form wi then the word problem is easily solved. A confluent rewriting system allows one to do precisely this. Although the choice of a canonical form can theoretically be made in an arbitrary fashion this approach is generally not computable. (Consider that an equivalence relation on a language can produce an infinite number of infinite classes.) If the language is well ordered then the order < gives a consistent method for defining minimal representatives, however computing these representatives may still not be possible. In particular, if a rewriting system is used to calculate minimal representatives then the order < should also have the property:
A < B → XAY < XBY for all words A,B,X,Y
This property is called translation invariance. An order that is both translation invariant and a well order is called a reduction order'. From the presentation of the monoid it is possible to define a rewriting system given by the relations R. If A x B is in R then either A < B in which case B → A is a rule in the rewriting system, otherwise A > B and A → B. Since < is a reduction order a given word W can be reduced W > W 1 > > W n where W n is irreducible under the rewriting system. However, depending on the rules that are applied at each Wi → Wi+1 it is possible to end up with two different irreducible reductions Wn ≠ W'm of W. However, if the rewriting system given by the relations is converted to a confluent rewriting system via the Knuth–Bendix algorithm, then all reductions are guaranteed to produce the same irreducible word, namely the normal form for that word. Description of the algorithm for finitely presented monoids
Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a reduction ordering among the words generated by (e. g., shortlex order). For each relation in , suppose Thus we begin with the set of reductions
First, if any relation can be reduced, replace and with the reductions. Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and overlap. Case 1: either the prefix of equals the suffix of , or vice versa. In the former case, we can write and ; in the latter case, and Case 2: either is completely contained in (surrounded by) , or vice versa. In the former case, we can write and ; in the latter case, and
Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to
After adding a rule to , remove any rules in that might have reducible left sides (after checking if such rules have critical pairs with other rules). Repeat the procedure until all overlapping left sides have been checked. Examples
A terminating example
Consider the monoid: We use the shortlex order. This is an infinite monoid but nevertheless, the Knuth–Bendix algorithm is able to solve the word problem. Our beginning three reductions are therefore
A suffix of (namely ) is a prefix of , so consider the word Reducing using , we get Reducing using , we get Hence, we get , giving the reduction rule
Similarly, using and reducing using and , we get Hence the reduction
Both of these rules obsolete , so we remove it. Next, consider by overlapping and Reducing we get , so we add the rule
Considering by overlapping and , we get , so we add the rule
These obsolete rules and , so we remove them. Now, we are left with the rewriting system
Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully. A non terminating example
The order of the generators may crucially affect whether the Knuth–Bendix completion terminates. As an example, consider the free Abelian group by the monoid presentation:
The Knuth–Bendix completion with respect to lexicographic order finishes with a convergent system, however considering the length lexicographic order it does not finish for there are no finite convergent systems compatible with this latter order. Generalizations
If Knuth–Bendix does not succeed, it will either run forever and produce successive approximations to an infinite complete system, or fail when it encounters an unorientable equation (i. e. an equation that it cannot turn into a rewrite rule). An enhanced version will not fail on unorientable equations and produces a ground confluent system, providing a semi algorithm for the word problem. The notion of logged rewriting discussed in the paper by Heyworth and Wensley listed below allows some recording or logging of the rewriting process as it proceeds. This is useful for computing identities among relations for presentations of groups. References
C. Sims. 'Computations with finitely presented groups.' Cambridge, 1994. Anne Heyworth and C. D. Wensley. "Logged rewriting and identities among relators." Groups St. Andrews 2001 in Oxford. Vol. I,'' 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.