Knuth-Bendix 완료 알고리즘

Knuth-Bendix 완성 알고리즘(Donald Knuth와 Peter^[1] Bendix의 이름을 따서 명명)은 일련의 방정식을 합류항 재작성 시스템으로 변환하기 위한 반결정 [2]^[3] 알고리즘입니다.알고리즘이 성공하면 지정된 대수의 단어 문제를 효과적으로 해결합니다.

Buckberger의 Gröbner 염기 계산 알고리즘은 매우 유사한 알고리즘입니다.독립적으로 개발되었지만, 다항환 이론에서 크누스-벤딕스 알고리즘의 인스턴스화로도 볼 수 있다.

서론

방정식 집합 E에 대해 연역적 폐쇄(δδE)는 임의의 순서로 E에서 방정식을 적용하여 도출할 수 있는 모든 방정식의 집합입니다.공식적으로는 E는 2치 관계, (δE)는 그 개서 클로저, (δE)는 (δE)의 등가 클로저로 간주된다.개서 규칙 집합 R의 경우, 그 연역적 폐쇄(⟶rR ∘∘R)는 말 그대로 같아질 때까지 왼쪽에서 오른쪽으로 규칙을 적용함으로써 확인할 수 있는 모든 방정식의 집합입니다.공식적으로 R은 다시 이진관계로 간주되며, (θR)은 그 개서폐쇄, (θR)는 그 반전, (θR θR)는 그 반사적 전이폐쇄의 관계성분(θR 및 θR)이다.

예를 들어, E $=$ { $1μx$ $= x -1, xμx$ $= 1,$ ( $xμy) μz$ = $xμ (yμz)}$ 가 군 공리일 $경우$ , 유도 사슬은

a -1 ((abb) ⁎ E （ aaa -1 ） ⟷ b \cdot E 1 b E b

는 a((abb)⁎ Eb가 E의 연역적 폐쇄의 멤버임을 나타낸다⁻¹.R = { $1 µx$ → $x -1,$ $x$ $µx \to$ 1, ( $x µy)$ → $x µx (y$ µz) }가 E의 "규칙" 버전인 $경우$ , 파생 사슬

(aaa -1) b b ⁎ R1 1 bb Rb 및 b ⟵ Rb

(aaa⁻¹)bb⁎R⁎R isRb가 R의 연역적 폐쇄의 구성원임을 입증한다.단, 규칙 $(xyy) zz$ → $x ((yzz)$ 의 오른쪽에서 왼쪽으로 적용이 허용되지 않으므로 위와 같은 a⋅(abb)) R⁎ R similar Rb를 도출할⁻¹ 수 있는 방법은 없습니다.

Knuth-Bendix 알고리즘은 항 사이의 방정식 집합 E와 모든 항의 집합에서 축소 순서(>)를 취하여 E와 연역적 폐쇄를 갖는 합류 및 종단 용어 개서 시스템 R을 구축하려고 시도합니다.E로부터의 결과를 증명하는 것은 종종 인간의 직관을 필요로 하지만, R로부터의 결과를 증명하는 것은 그렇지 않다.자세한 내용은 Conversence(추상 재작성)를 참조하십시오.#군론의 예를 들어 E와 R의 양쪽 모두를 사용한 동기 부여 예.

규칙.

항간 방정식의 집합 E가 주어지면 다음 추론 규칙을 사용하여 동등한 수렴 항 개서 시스템으로 변환할 수 있습니다(가능한 경우).^[4]^[5]이러한 순서는 모든 조건의 집합에 대한 사용자 지정 감소 순서(>)에 기초합니다. 다음과 같은 $경우$ , ( $s$ → t $) l$ ( $l$ $\to$ r)를 정의함으로써 다시 쓰기 규칙 집합에 대한 충분한 근거가 있는 순서(예:)로 승격됩니다.

s> $e$ in 、 mentment 、 ,ment 、
$s$ 와 l은 말 그대로 $비슷하고$ t > $r$ 입니다.

삭제	§ E440s = s}	, R »	⊢	§ E	, R »
작성하다	§ E	, R → t } ›	⊢	§ E	, R → u} ›	$trru$ 의 $경우$
심플화	e E { = t }	, R »	⊢	e E { = u }	, R »	$trru$ 의 $경우$
오리엔트	e E { = t }	, R »	⊢	§ E	, R → t } ›	s > $t$ 의 $경우$
접다	§ E	, R → t } ›	⊢	e E{{u = t}	, R »	s $rR$ u $by$ l → $r$ $with$ ( $s$ → t) $($ ( $l$ $\to$ r)인 $경우$
추론	§ E	, R »	⊢	e E { = t }	, R »	$(s, t)$ 가 R의 중요한 쌍인 경우

예

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,410)

이 예제의 다른 프레젠테이션에 대해서는, 「단어 문제(수학)」도 참조해 주세요.

그룹 이론에서의 문자열 재작성 시스템

계산 그룹 이론에서 중요한 사례는 발생기의 산물로서 최종적으로 제시되는 그룹의 요소 또는 코셋에 표준 라벨을 부여하는 데 사용될 수 있는 문자열 개서 시스템이다.이 특별한 케이스가 이 섹션의 초점입니다.

그룹 이론의 동기 부여

크리티컬 쌍의 약어에는 모든 크리티컬쌍이 수렴하는 경우에만 용어 개서 시스템이 로컬로 수렴(또는 약하게 수렴)되어 있다고 기술되어 있습니다.또한, 우리는 (추상) 개서 시스템이 강하게 정규화되고 약하게 합류하는 경우, 개서 시스템은 합류한다는 Newman의 약어를 가지고 있다.따라서 강력한 정규화 속성을 유지하면서 모든 중요한 쌍을 수렴하기 위해 용어 재작성 시스템에 규칙을 추가할 수 있으면 결과적으로 재작성 시스템이 합류하게 됩니다.

최종 표시된 $M=\langle X\mid R\rangle$ M $=$ X $M=\langle X\mid R\rangle$ R ${\$ { $displaystyle$ M=\ $langle$ X\ $mid$ R $\rangle }$ 을 $M=\langle X\mid R\rangle$ 생각해 보겠습니다. 여기서 X는 생성기의 유한 집합이고 R은 X에 대한 정의 관계 집합입니다.X를 X의 모든 단어 집합(즉, X에 의해 생성된 자유 모노이드)이라고 하자^*.관계 R은 X*에 등가 관계를 생성하므로 M의 원소는 R 아래의 X의^* 등가 클래스로 간주할 수 있다.각 클래스에 대해₁ {w₂, w, ... } 표준대표_k w를 선택하는 것이 바람직하다.이 표현은 클래스 내의 각 단어_k w에 대해 정규 형식 또는 정규 형식이라고 불립니다.각 w에_k 대해 그 정규형_i w를 결정하는 계산 가능한 방법이 있으면 단어 문제를 쉽게 해결할 수 있다.합류 개서 시스템은 이것을 정확하게 할 수 있게 해준다.

표준 형식의 선택은 이론적으로 임의적인 방법으로 이루어질 수 있지만, 이 접근법은 일반적으로 계산할 수 없습니다. (언어상의 동등관계는 무한한 수의 클래스를 생성할 수 있다는 것을 고려하십시오.)언어가 잘 정렬되어 있는 경우, 순서<는 최소한의 표현을 정의하는 일관된 방법을 제공하지만, 이러한 표현을 계산하는 것은 여전히 불가능할 수 있습니다.특히 개서 시스템을 사용하여 최소 대표자를 계산할 경우 주문 <에는 다음 속성도 포함되어 있어야 합니다.

A < B → XAY < XBY (모든 단어 A, B, X, Y)

이 속성을 변환 불변성이라고 합니다.변환불변순순서 및 정상순서인 순서는 모두 감소순서라고 불립니다.

이 모노이드의 제시로부터 관계 R에 의해 주어지는 개서계를 정의할 수 있다.A x B 가 R 에 있는 경우는, A < B → A 가 개서 시스템의 룰이 됩니다.그 이외의 경우는 A > B 및 A → B 입니다.< 는 축소 순서이므로, 소정의 단어 W 는 W > W_1 > ...을 줄일 수 있습니다.> W_n (W_n은 개서 시스템에서는 축소할 수 없습니다).그러나 각 W_i → W에서_i+1 적용되는 규칙에 따라 W의 두 가지 다른 환원 불가능 W_n of _mW'가 될 수 있다.그러나 관계에서 주어진 개서 시스템을 Knuth-Bendix 알고리즘을 통해 합류 개서 시스템으로 변환하면 모든 감소가 동일한 축소 불가능한 단어, 즉 해당 단어의 정규 형식을 생성하도록 보장됩니다.

최종적으로 제시된 모노이드에 대한 알고리즘 설명

프레젠테이션 $\langle X\mid R\rangle$ 「 $\langle X\mid R\rangle$ 」 $\langle X\mid R\rangle$ $\langle X\mid R\rangle$ displaystyle \ $langle X\mid R$ \rangle $\langle X\mid R\rangle$ 가 $있다고$ 합니다 $.여기$ 서 X $(\$ $displaystyle$ X $)$ 는 $X$ 제너레이터 세트, $R$ (\ $displaystyle$ R $)$ 는 $R$ 개서 시스템을 제공하는 관계 세트입니다.X{\ $displaystyle$ X $X$ 에서 생성된 단어 중 축소 순서 $<\displaystyle <\$ displaystyle>이 $<$ 있다고 가정합니다(예를 들어 shortlex 순서). $R의$ 각 $P_{i}=Q_{i}$ $P_{i}=Q_{i}$ $P_{i}=Q_{i}$ $displaystyle$ $P_{i$ }= $Q_{i$ })에 $P_{i}=Q_{i}$ 대해 $Q_{i}<P_{i}$ $Q_{i}<P_{i}$ $(\$ 를 $Q_{i}<P_{i}$ 합니다. $P_{i$ 따라서 먼저 일련의 $P_{i}\rightarrow Q_{i}$ $P_{i}\rightarrow Q_{i}$ $P_{i}\rightarrow Q_{i}$ $P_{i}\rightarrow Q_{i}$ $($ 표시 $스타일$ P_ ${i}\오른쪽$ 화살표 $Q_{i$ 부터 시작합니다.

First, if any relation $P_{i}=Q_{i}$ can be reduced, replace $P_{i}$ and $Q_{i}$ with the reductions.

다음으로, 추가의 삭감(즉, 룰의 개서)을 추가해, 합류의 예외를 배제합니다. $(\$ })와 $P_{i}$ $(\$ 가 $P_{j}$ 겹친다고 가정합니다.

케이스 1: 프리픽스 $(\$ })는 $P_{i}$ $(\$ 의 서픽스와 같거나 그 반대입니다.전자의 경우 $P_{i}=BC$ $P_{i}=BC$ $P_{i}=BC$ { $display style$ P _ { i } $=$ 라고 쓸 수 있습니다. $BC}$ $P_{j}=AB$ $P_{j}=AB$ $=$ $P_{j}=AB$ $(\displaystyle P_{j$ }= $AB$ 후자의 $P_{i}=AB$ $P_{i}=AB$ $P_{i}=AB$ $P_{i}=AB$ { $displaystyle P_{i$ } $=$ $AB}$ $P_{j}=BC$ $P_{j}=BC$ $=$ $P_{j}=BC$ C $(\displaystyle$ P_ ${j$ }= $BC$
케이스 2: $($ 스타일 P_ ${i})$ 는 $P_{i}$ $($ P_ ${j$ 에 완전히 포함되거나(주변으로 둘러싸여 있음) 그 반대입니다.전자의 경우 $P_{i}=B$ $=$ $(\displaystyle P_{i$ }= $B$ $P_{j}=ABC$ $=$ $P_{j}=ABC$ $(\displaystyle P_{j$ }=)로 표기할 수 있습니다. $ABC$ 후자의 $P_{i}=ABC$ $P_{i}=ABC$ $=$ $P_{i}=ABC$ $P_{i}=ABC$ C $(\displaystyle$ P_ ${i$ }= $ABC}$ $P_{j}=B$ $P_{j}=B$ $=$ ({ $displaystyle P_{j$ }= $B$

$먼저$ $($ 스타일 $P_$ ${i$ })를 $P_{i}$ 사용하여 A B C $(디스플레이 스타일$ $ABC$ $)$ 를 $ABC$ 줄인 다음 $($ P_ ${j})$ 를 $P_{j}$ $P_{j}$ 합니다. $r_{1},r_{2}$ $({$ 결과를 $r_{1},r_{2}$ 호출합니다. $r_{1}\neq r_{2}$ 1 $r_{1}\neq r_{2}$ $r_{1}\neq r_{2}$ 2 { $displaystyle r$ _ { $1}$ \ $neq r$ _ {2} $r_{1}\neq r_{2}$ }인 $r_{1}\neq r_{2}$ 컨버전스가 실패할 수 있는 인스턴스가 있습니다. $\max r_{1},r_{2}\rightarrow \min r_{1},r_{2}$ R {\ $\max r_{1},r_{2}\rightarrow \min r_{1},r_{2}$ \ $\max r_{1},r_{2}\rightarrow \min r_{1},r_{2}$ { $\max r_{1},r_{2}\rightarrow \min r_{1},r_{2}$ } 를 $\max r_{1},r_{2}\rightarrow \min r_{1},r_{2}$ R{\ $displaystyle$ $\max r_{1},r_{2}\rightarrow \min r_{1},r_{2}$ R $R$ 에 $R$ 합니다.

R ${\displaystyle$ R $R$ 에 규칙을 추가한 후 R{\ $displaystyle$ R $}$ 에서 $R$ 축소 가능한 왼쪽이 있을 수 있는 규칙을 삭제합니다(다른 규칙과 중요한 쌍이 있는지 확인한 후).

중복되는 모든 좌측이 확인될 때까지 이 절차를 반복합니다.

예

종료 예

모노이드를 고려합니다.

\langle x,y\mid x^{3}=y^{3}=(xy)^{3}=1\rangle

\langle x,y\mid x^{3}=y^{3}=(xy)^{3}=1\rangle

,

\langle x,y\mid x^{3}=y^{3}=(xy)^{3}=1\rangle

∣

\langle x,y\mid x^{3}=y^{3}=(xy)^{3}=1\rangle

=

\langle x,y\mid x^{3}=y^{3}=(xy)^{3}=1\rangle

3

\langle x,y\mid x^{3}=y^{3}=(xy)^{3}=1\rangle

(

\langle x,y\mid x^{3}=y^{3}=(xy)^{3}=1\rangle

y ) 3

\langle x,y\mid x^{3}=y^{3}=(xy)^{3}=1\rangle

=

1

{

displaystyle

\

sparle x

, y \

mid x

} =

\langle x,y\mid x^{3}=y^{3}=(xy)^{3}=1\rangle

y^{3} = (

xy

)^

3}

=

\langle x,y\mid x^{3}=y^{3}=(xy)^{3}=1\rangle

1 \ rangle

\langle x,y\mid x^{3}=y^{3}=(xy)^{3}=1\rangle

。

Shortlex 오더를 사용합니다.이것은 무한 모노이드이지만, 그럼에도 불구하고 Knuth-Bendix 알고리즘은 단어 문제를 해결할 수 있습니다.

따라서 처음 세 가지 절감은

{\displaystyle x^{3}\오른쪽 화살표 1)

(1)

{\displaystyle y^{3}\오른쪽 화살표 1)

(2)

(xy)^{3}\rightarrow 1

(xy)^{3}\rightarrow 1

y )

(xy)^{3}\rightarrow 1

(xy)^{3}\rightarrow 1

(xy)^{3}\rightarrow 1

{{

displaystyle (xy)^{3}\right arrow

1

(xy)^{3}\rightarrow 1

(3)

$x^{3}$ 3 $($ $xisplaystyle$ x $^{$ $3$ $x$ 의 접미사는 ( $(xy)^{3}=xyxyxy$ $(xy)^{3}=xyxyxy$ $=$ $(xy)^{3}=xyxyxy$ $(xy)^{3}=xyxyxy$ $(xy)^{3}=xyxyxy$ $(xy)^{3}=xyxyxy$ { $xy$ $style$ $(xy)^{$ $3}=$ $xyxy$ 의 $(xy)^{3}=xyxyxy$ 접두사이므로 $x^{3}yxyxy$ $x^{3}yxyxy$ $x^{3}yxyxy$ $xy$ $.$ xystyle을 사용하여 $yxy .$ xy $x^{3}yxyxy$ $xy$ .xystyle을 $줄입니다$ . $({$ x $^{2$ 따라서 y $yxyxy=x^{2}$ $yxyxy=x^{2}$ $yxyxy=x^{2}$ y $yxyxy=x^{2}$ $yxyxy=x^{2}$ 2({ $displaystyle yxxy=x^{$ 2 $yxyxy=x^{2}$ 가 $yxyxy=x^{2}$ 축소 규칙이 지정됩니다.

yxyxy\rightarrow x^{2}

yxyxy\rightarrow x^{2}

yxyxy\rightarrow x^{2}

yxyxy\rightarrow x^{2}

y

yxyxy\rightarrow x^{2}

yxyxy\rightarrow x^{2}

2 {

display yxy

\

rightarrow

x {2

} }

。

(4)

마찬가지로 x $xyxyxy^{3}$ $xyxyxy^{3}$ y $xyxyxy^{3}$ y $xyxyxy^{3}$ $({$ 3 $xyxyxy^{3}$ }})을 사용하고 (2)와 (3)을 사용하여 축소를 $xyxyx=y^{2}$ $xyxyx=y^{2}$ y $xyxyx=y^{2}$ $xyxyx=y^{2}$ $xyxyx=y^{2}$ $xyxyx=y^{2}$ ({ $display style$ xyxyx $=y^{2$ 를 $xyxyx=y^{2}$ 수 있습니다.따라서 축소가 됩니다.

xyxyx\rightarrow y^{2}

xyxyx\rightarrow y^{2}

xyxyx\rightarrow y^{2}

xyxyx\rightarrow y^{2}

x

xyxyx\rightarrow y^{2}

xyxyx\rightarrow y^{2}

2 (\

style xyxx\rightarrow

y

^{2

(5)

이 두 규칙 모두 사용되지 않기 때문에(3) 삭제합니다.

다음으로 (1)과 (5)을 겹쳐서 $x^{3}yxyx$ $x^{3}yxyx$ x $x^{3}yxyx$ {\ $displaystyle$ x $^{3$ } $yxyx}$ 를 $x^{3}yxyx$ $x^{3}yxyx$ 합니다. $yxyx=x^{2}y^{2}$ y x $yxyx=x^{2}y^{2}$ x $yxyx=x^{2}y^{2}$ $yxyx=x^{2}y^{2}$ $yxyx=x^{2}y^{2}$ $yxyx=x^{2}y^{2}$ ({ $displaystyle yxx=x^{2}y^{2$ 가 되므로 규칙을 추가합니다.

yxyx\rightarrow x^{2}y^{2}

yxyx\rightarrow x^{2}y^{2}

yxyx\rightarrow x^{2}y^{2}

x

yxyx\rightarrow x^{2}y^{2}

yxyx\rightarrow x^{2}y^{2}

yxyx\rightarrow x^{2}y^{2}

y

yxyx\rightarrow x^{2}y^{2}

({

display yxyx\rightarrow x^{2}y^{2

(6)

(1)과 (5)를 $xyxyx^{3}$ 으로써 $({$ style $xyxx^{3})$ 을 $xyxyx^{3}$ $xyxyx^{3}$ 하면 $xyxy=y^{2}x^{2}$ $({$ xyxy $=y^{$ 2} $x^{2$ 를 $xyxy=y^{2}x^{2}$ 수 있으므로 규칙을 추가합니다.

y^{2}x^{2}\rightarrow xyxy

y^{2}x^{2}\rightarrow xyxy

y^{2}x^{2}\rightarrow xyxy

2

y^{2}x^{2}\rightarrow xyxy

y^{2}x^{2}\rightarrow xyxy

y^{2}x^{2}\rightarrow xyxy

y^{2}x^{2}\rightarrow xyxy

{

display

y ^ {

2} x^

{2

}

\

rightarrow xyxy

} 。

(7)

이러한 낡은 규칙(4)과 (5)이 있기 때문에 삭제합니다.

이제 우리는 개서 시스템을 남겨두고 있다.

{\displaystyle x^{3}\오른쪽 화살표 1)

(1)

{\displaystyle y^{3}\오른쪽 화살표 1)

(2)

yxyx\right 화살표 x^{2}y^{2}

(6)

y^{2}x^{2}\rightarrow xyxy

y^{2}x^{2}\rightarrow xyxy

y^{2}x^{2}\rightarrow xyxy

2

y^{2}x^{2}\rightarrow xyxy

y^{2}x^{2}\rightarrow xyxy

y^{2}x^{2}\rightarrow xyxy

y^{2}x^{2}\rightarrow xyxy

{

display

y ^ {

2} x^

{2

}

\

rightarrow xyxy

} 。

(7)

이러한 규칙의 중복을 체크하면, 합류의 잠재적인 실패는 발견되지 않습니다.따라서 합류 개서 시스템이 있으며 알고리즘은 정상적으로 종료됩니다.

종료되지 않는 예

발전기의 순서는 Knuth-Bendix 완성이 종료되는지 여부에 결정적으로 영향을 미칠 수 있다.예를 들어, 모노이드의 표현에 의한 자유 아벨 군을 생각해 봅시다.

\displaystyle x,y,x^{-1},\xy=yx,xx^{-1}=x^{-1}x=y^{-1}=y^{-1}y=1\rangle.}

사전식 순서와 관련한 Knuth–Bendix 완료)<>)− 1<> 베<>y − 1{\displaystyle x<, x^{)}<, y<, y^{)}}를 융합 시스템과 그length-lexicographic 위해)<>를 고려하지 않을래, 베<>)− 1<>y − 1{\displaystyle x<, y<, x^{)}<, y^{)}}그것 f.을 끝내지 않는다수 있는 유한 수렴 sy 있다.이 후자의 ^[6]순서와 호환성이 있는 스템.

일반화

Knuth-Bendix가 성공하지 못하면 무한 완전 시스템에 대한 연속적인 근사치를 생성하거나 방향성이 없는 방정식(즉, 다시 쓰기 규칙으로 바꿀 수 없는 방정식)을 만나면 실패합니다.향상된 버전은 방향성이 없는 방정식에서 실패하지 않고 단어 문제에 ^[7]대한 반알고리즘을 제공하는 접지 합류 시스템을 생성합니다.

Heyworth와 Wensley가 아래에 기재한 문서에서 설명한 기록 개서의 개념을 통해 개서 프로세스의 진행 중 일부 기록 또는 기록을 수행할 수 있습니다.이것은 그룹의 프레젠테이션을 위한 관계 간의 아이덴티티를 계산하는 데 유용합니다.

레퍼런스

^ D. 크누스, 속성문법의 창시
^ Jacob T. Schwartz; Domenico Cantone; Eugenio G. Omodeo; Martin Davis (2011). Computational Logic and Set Theory: Applying Formalized Logic to Analysis. Springer Science & Business Media. p. 200. ISBN 978-0-85729-808-9.
^ Hsiang, J.; Rusinowitch, M. (1987). "On word problems in equational theories" (PDF). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 267. p. 54. doi:10.1007/3-540-18088-5_6. ISBN 978-3-540-18088-3., 페이지 55
^ Bachmair, L.; Dershowitz, N.; Hsiang, J. (Jun 1986). "Orderings for Equational Proofs". Proc. IEEE Symposium on Logic in Computer Science. pp. 346–357.
^ N. Dershowitz; J.-P. Jouannaud (1990). Jan van Leeuwen (ed.). Rewrite Systems. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 243–320. 여기서: 제8.1절, 페이지 293
^ V. Diekert; A.J. Duncan; A.G. Myasnikov (2011). "Geodesic Rewriting Systems and Pregroups". In Oleg Bogopolski; Inna Bumagin; Olga Kharlampovich; Enric Ventura (eds.). Combinatorial and Geometric Group Theory: Dortmund and Ottawa-Montreal conferences. Springer Science & Business Media. p. 62. ISBN 978-3-7643-9911-5.
^ Bachmair, Leo; Dershowitz, Nachum; Plaisted, David A. (1989). "Completion Without Failure" (PDF). Rewriting Techniques: 1–30. doi:10.1016/B978-0-12-046371-8.50007-9. Retrieved 24 December 2021.

D. Knuth; P. Bendix (1970). J. Leech (ed.). Simple Word Problems in Universal Algebras (PDF). Pergamon Press. pp. 263–297.
Gérard Huet (1981). "A Complete Proof of Correctness of the Knuth-Bendix Completion Algorithm" (PDF). J. Comput. Syst. Sci. 23 (1): 11–21. doi:10.1016/0022-0000(81)90002-7.
심즈'그룹으로 구성된 컴퓨터'케임브리지, 1994년
앤 헤이워스와 CD.D.웬슬리."다시 쓴 기록과 릴레이터 간의 ID"그룹 St. 옥스퍼드의 앤드루스 2001. 제1권, 256~276, 런던 수학케임브리지 대학교 사회과 강의 노트 경, 304.프레스, 캠브리지, 2003.

외부 링크

[1] D. 크누스, 속성문법의 창시

[SchwartzCantone2011-2] Jacob T. Schwartz; Domenico Cantone; Eugenio G. Omodeo; Martin Davis (2011). Computational Logic and Set Theory: Applying Formalized Logic to Analysis. Springer Science & Business Media. p. 200. ISBN 978-0-85729-808-9.

[3] Hsiang, J.; Rusinowitch, M. (1987). "On word problems in equational theories" (PDF). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 267. p. 54. doi:10.1007/3-540-18088-5_6. ISBN 978-3-540-18088-3., 페이지 55

[4] Bachmair, L.; Dershowitz, N.; Hsiang, J. (Jun 1986). "Orderings for Equational Proofs". Proc. IEEE Symposium on Logic in Computer Science. pp. 346–357.

[5] N. Dershowitz; J.-P. Jouannaud (1990). Jan van Leeuwen (ed.). Rewrite Systems. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 243–320. 여기서: 제8.1절, 페이지 293

[BogopolskiBumagin2011-6] V. Diekert; A.J. Duncan; A.G. Myasnikov (2011). "Geodesic Rewriting Systems and Pregroups". In Oleg Bogopolski; Inna Bumagin; Olga Kharlampovich; Enric Ventura (eds.). Combinatorial and Geometric Group Theory: Dortmund and Ottawa-Montreal conferences. Springer Science & Business Media. p. 62. ISBN 978-3-7643-9911-5.

[7] Bachmair, Leo; Dershowitz, Nachum; Plaisted, David A. (1989). "Completion Without Failure" (PDF). Rewriting Techniques: 1–30. doi:10.1016/B978-0-12-046371-8.50007-9. Retrieved 24 December 2021.

[1]

[3]

[4]

[5]

[6]

[7]

v t 도널드 크누스
출판물	컴퓨터 프로그래밍의 기술 '노래의 복잡성' 컴퓨터와 식자 설정 구체적인 수학 초현실적인 숫자 컴퓨터 과학자가 좀처럼 언급하지 않는 것 선택한 논문 시리즈
소프트웨어	TeX 메타폰트 믹스(믹스) MMIX GNU MDK)
폰트	AMS 오일러 최신 컴퓨터 콘크리트 로마자
리터럴 프로그래밍	웹 CWEB
알고리즘	크누스의 알고리즘 X Knuth-Bendix 완료 알고리즘 크누스-모리스-프랫 알고리즘 크누트 셔플 로빈슨-센스테드-크누트 통신 Trabb Pardo-Knuth 알고리즘 다이크스트라 알고리즘의 일반화 크누스의 심패스 알고리즘
다른.	댄싱 링크 Knuth 보상 조회 크누트상 크누스의 위 화살표 표기법 남자 또는 남자 테스트 사분위수 기저 - yllion 도량형 포트르제비계

Search