다시 쓰기

수학, 컴퓨터 과학 및 논리학에서 다시 쓰기는 공식의 밑그림을 다른 용어로 대체하는 광범위한 방법을 다룹니다. 이러한 방법은 시스템(재작성 시스템, 재작성 엔진 ^[1][2]또는 축소 시스템이라고도 함)을 재작성함으로써 달성될 수 있습니다. 가장 기본적인 형태로 개체 집합과 개체를 변환하는 방법에 대한 관계로 구성됩니다.

다시 쓰기는 결정적이지 않을 수 있습니다. 용어를 다시 쓰는 하나의 규칙은 해당 용어에 여러 가지 방법으로 적용될 수도 있고, 둘 이상의 규칙이 적용될 수도 있습니다. 그런 다음 시스템을 다시 쓰는 것은 한 용어를 다른 용어로 변경하는 알고리즘이 아니라 가능한 규칙 응용 프로그램의 집합을 제공합니다. 그러나 적절한 알고리즘과 결합하면 다시 쓰기 시스템은 컴퓨터 프로그램으로 볼 수 있으며 여러 정리 증명 및^[3] 선언적 프로그래밍 언어는 용어 다시 쓰기를 기반으로 합니다.^[4][5]

예시사례

논리

논리학에서 공식의 연결 정상 형태(CNF)를 구하는 절차는 재작성 시스템으로 구현될 수 있습니다.^[6] 그러한 시스템의 예에 대한 규칙은 다음과 같습니다.

${\displaystyle \mathrm{\neg }}$ ${\displaystyle \mathrm{A}}$ → A ${\displaystyle$ \$neg$ \$neg$ A$\$to A} (이중 네거티브 제거)

$A ∧$ ${\displaystyle \mathrm{B}}$ ${\displaystyle \mathrm{)}}$ ${\displaystyle \mathrm{\to }}$ ${\displaystyle \mathrm{\neg \; A}}$ ∨ ¬ $B${\$displaystyle$ \$neg (A\land$ B$)\$ to \neg A\lor \neg B} (De Morgan's laws)

${\displaystyle \neg(A\lor B)\to \neg A\land \neg B}$

$A$ ∧${\displaystyle }$B)${\displaystyle \vee }$ C$→$(A ∨${\displaystyle }$C) ∧${\displaystyle }$(B ∨ C) {\displaystyle (A\land B)\lor C\to (A\lor C)\lor C (B\lor C${\displaystyle )\}\; (dis}$trib 효율)

${\displaystyle A\lor (B\land C)\to (A\lor B)\land (A\lor C),}$^[주1]

여기서 기호( → {\$displaystyle \to$ $\})$는 규칙의 왼쪽과 일치하는 표현을 오른쪽에 의해 형성된 표현으로 다시 쓸 수 있음을 나타내며 기호는 각각 하위 표현을 나타냅니다. 이러한 시스템에서 각 규칙은 왼쪽이 오른쪽과 동일하도록 선택되며, 결과적으로 왼쪽이 하위 표현식과 일치할 때 해당 하위 표현식을 왼쪽에서 오른쪽으로 다시 쓰면 전체 표현식의 논리적 일관성과 값이 유지됩니다.

산술

용어 다시 쓰기 시스템을 사용하여 자연수에 대한 산술 연산을 계산할 수 있습니다. 이를 위해서는 각 해당 숫자를 용어로 인코딩해야 합니다. 가장 간단한 인코딩은 상수 0(zero)과 계승 함수 S를 기반으로 한 페아노 공리에서 사용되는 인코딩입니다. 예를 들어, 숫자 0, 1, 2 및 3은 각각 항 0, S(0), S(S(0) 및 S(S(0))로 표시됩니다. 그런 다음 다음 용어 다시 쓰기 시스템을 사용하여 주어진 자연수의 합과 곱을 계산할 수 있습니다.^[7]

${\displaystyle {\begin{aligned} 스타일}A+0&\to A&{\textrm {(1)}},\\A+S(B)&\to S(A+B)&{\textrm {(2)}},\\A\cdot 0&\to 0&{\textrm {(3)}},\\A\cdot S(B)&\to A+(A\cdot B)&{\textrm {(4)}}.\end{align}}}$

예를 들어 2+2를 4로 계산하면 다음과 같이 용어 재작성으로 복제할 수 있습니다.

${\displaystyle S(S(0))+S(S(0))}$ ${\displaystyle \;\;{\stackrel {(2)}{\to }}\;\;}$ ${\displaystyle S(\;S(S(0))+S(0)\;)}$ ${\displaystyle \;\;{\stackrel {(2)}{\to }}\;\;}$ ${\displaystyle S(S(\;S(S(0))+0\;))}$ ${\displaystyle \;\;{\stackrel {(1)}{\to }}\;\;}$ ${\displaystyle S(S(S(S(0)))),}$

여기서 규칙 번호는 다시 쓰기 화살표 위에 제공됩니다.

또 다른 예로, 2 ⋅2의 계산은 다음과 같습니다.

${\displaystyle S(S(0))\cdot S(S(0))}$ ${\displaystyle \;\;{\stackrel {(4)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))\cdot S(0)}$ ${\displaystyle \;\;{\stackrel {(4)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))+S(S(0))\cdot 0}$ ${\displaystyle \;\;{\stackrel {(3)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))+0}$ ${\displaystyle \;\;{\stackrel {(1)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))}$ ${\displaystyle \;\;{\stackrel {\textrm {s.a.}}{\to }}\;\;}$ ${\displaystyle S(S(S(S(0)))),}$

여기서 마지막 단계는 이전 예제 계산으로 구성됩니다.

언어학

언어학에서, 재작성 규칙이라고도 불리는 구문 구조 규칙은 언어의 문법적으로 올바른 문장을 생성하는 수단으로서 ^[8]생성 문법의 일부 시스템에서 사용됩니다. 이러한 규칙은 일반적으로 ${\displaystyle \mathrm{A}}$ → X {\$displaystyle$ ${\rm {A\rightarrow$ X$}}$ 형태를 취하며$,$ 여기서 A는 명사구나 문장과 같은 구문 범주 레이블이고, X는 그러한 레이블이나 형태소의 시퀀스이며, 문장의 구성 구조를 생성할 때 A가 X로 대체될 수 있다는 사실을 나타냅니다. 예를 들어, 규칙 $S$ → ${\displaystyle \mathrm{N}}$ ${\displaystyle \text{PV}}${\$displaystyle${\$rm {S\rightarrow NP\VP}}$은 문장이 명사구(NP)와 동사구(VP)로 구성될 수 있음을 의미합니다. 추가 규칙은 명사구와 동사구가 어떤 하위 constituent로 구성될 수 있는지 등을 지정합니다.

추상 재작성 시스템

위의 예에서 추상적인 방식으로 시스템을 다시 쓰는 것을 생각할 수 있음이 분명합니다. 개체 집합과 개체를 변환하는 데 적용할 수 있는 규칙을 지정해야 합니다. 이 개념의 가장 일반적인 (단일 차원) 설정을 추상 축소 시스템^[9] 또는 추상 재작성 시스템(약칭 ARS)이라고 합니다.^[10] ARS는 A에 대한 이항 관계 →와 함께 단순히 객체들의 집합 A를 축소 관계, 다시 쓰기 관계 또는 그냥 축소라고 합니다.

많은 개념과 표기법은 ARS의 일반적인 설정에서 정의할 수 있습니다. $∗$ ${\displaystyle$ {\$overset {*}{\$rightarr${\displaystyle \stackrel{}{o}}$w}}는 $→$ ${\displaystyle$ \rightarrow}의 반사형 과도 폐${\displaystyle \stackrel{}{쇄}}$입니다. ↔ {\displaystyle \leftrightar${\displaystyle \stackrel{}{r}}$ow}는 → {\displaystyle \rightarrow}의 $대칭$ 폐쇄입니다. ${\displaystyle \stackrel{}{\leftrightarrow }}$$\ast$ ${\displaystyle$ {\$overset {*}{\$leftrightarr${\displaystyle \stackrel{}{o}}$w}}는 $$ ${\displaystyle$ \rightarrow}의 반사형 전이 대칭 폐쇄입니다. ARS의 단어 문제는 $x$와 y가 주어지면 x ↔ ∗ y {\$displaystyle x{\$overset ${*}{\leftrightarrow$ 여부를 결정합니다. A의 객체 x가 ${\displaystyle A}$에 x → y${\displaystyle$ x$rightarrow$ y}와 $같은$ 다른 y가 존재하면 축소 가능이라고 하고, 그렇지 않으면 축소 불가능 또는 정규 형식이라고 합니다. $만약$ $x$ → ∗ y${\displaystyle x{\stackrel {*}{\rightarrow$ y}이고, y는 축소할 수 없습니다. x의 정규 형태가 유일하다면, 이것은 $일반적$으로 x ↓ {\$displaystyle$ x${\downarrow}}$로 표시됩니다$.$ 모든 물체가 적어도 하나의 정규 형태를 가지면 ARS를 정규화라고 합니다. ${\displaystyle }$$x$ ↓ ${\displaystyle y}$ {\$displaystyle$ x$\downarrow y}$ 또는 x와 y는 ${\displaystyle x}$ $→$ ${\displaystyle \ast }$ ${\displaystyle z}$ ← ∗ y {\$displaystyle$x{\$overset {*}{\rightarrow}}z${\$overset$leftarrow}}y} 속성의 일부 z가 있는 경우 연결할 수 있다고 합니다. $만약$ ${\displaystyle x}$ ↔$$∗y {\$displaystyle$ x${\overset {*}{\leftrightarrow}}{\$downarrow y$}$가 x ↓ y${\displaystyle$ x$\backslash$downarrow y}를 의미한다면 ARS는 Church-Roser 속성을 가진다고 합니다. 모든 w, x에 대하여 ARS는 컨플루언트입니다. A에서 $y$는 x ← ∗ w → ∗ y {\$displaystyle$x{\$overset {*}{\leftarrow}}$w{\$overset {*}{\$$rightarrow$}}는$x$ ↓ $y${\$displaystyle$x\downarrow y}를 의미합니다. ARS는 모든 w, x인 경우에만 로컬로 컨플루언트됩니다. A에서 x ← w → ${\displaystyle y}$ $\{\backslash$$displaystyle$ x\$leftarrow$w\$rightarrow$ y}는 x$$↓ y {\displaystyle x{\mathbin {\downarrow}}를 의미합니다. 무한 체인 x 0 → x 1 → x 2 → ⋯ {\displaystyle x_{0}\rightarrow x_{1}\rightarrow x_{2}\rightarrow \cdots}가 없는 경우 ARS가 종료되거나 종료되지 않는다고 합니다. 합류하고 끝나는 ARS를 수렴 또는 정준이라고 합니다.

추상적 재작성 시스템의 중요한 정리는 ARS가 Church-Roser 속성인 Newman의 보조정리(종료 ARS가 국부적으로 합류하는 경우에만 합류)와 일반적으로 ARS에 대한 단어 문제는 결정할 수 없다는 것입니다.

문자열 재작성 시스템

SRS(String Rewriting System)는 Semi-Thue 시스템으로도 알려져 있으며 알파벳 위의 문자열(단어)의 자유 모노이드 구조를 이용하여 재작성 관계 $R{\displaystyle }$ ${\display R}$을$$일부 규칙의 왼쪽 및 오른쪽을 각각 서브스트링으로 포함하는 알파벳의 모든 문자열로 확장합니다. 형식적으로 세미-Thue 시스템은 투플$($σ, R) ${\displaystyle(\Sigma$, R)}이며$,$ $여기$서 σ${\displaystyle$ \Sigma}는 (일반적으로 $유한$한)$알파벳이고,$R {\displaystyle R}은 알파벳의 일부(고정된) 문자열 사이의 이진 관계이며, 이를 재작성 규칙 집합이라고 합니다. σ$$∗${\$displaystyle \Sigma^{*}의 R ${\displaystyle {}^{}}$displaystyle {\underset {R}{\rightarrow}}에서 R {\$displaystyle$ R}에 의해 유도된 1단계 재작성 관계 → ${\displaystyle \underset{}{}}$ ${\displaystyle \{\backslash }$displaystyle {R}{\rightarrow}}는 다음과 같이 정의됩니다. 만약 s, t ∗ σ {\displaystyle s,t\in \Sigma^{*}의 \displaystyle s,t\가 임의의 문자열이라면, then ${\displaystyle s{\underset {R}{\rightarrow }}t}$ if there exist ${\displaystyle x,y,u,v\in \Sigma ^{*}}$ such that ${\displaystyle s=xuy}$, ${\displaystyle t=xvy}$, and ${\displaystyle uRv}$. → ${\displaystyle \underset{}{}}$ ${\displaystyle \{\backslash }$displaystyle ${\$$underset$ {R$}{\rightarrow$}}는 σ ∗ {\displaystyle \Sigma^{*}}의 관계이므로, 쌍(σ ∗, → R) {\displaystyle(\Sigma^{*}, {\underset {R}{\rightarrow}})은 추상 재작성 시스템의 정의에 맞습니다. 빈 문자열이 σ ∗${\$displaystyle $\backslash$$Sigma$ ^{*}}에 있으므로 $R${\displaystyle R}은$$→ R {\$displaystyle${\$underset$ {R$\}\{\backslash$rightarrow}}의 ${\displaystyle \underset{}{}}$ 집합입니다.$관계 R${\displaystyle R}이 대칭이면 시스템을 Thue 시스템이라고 합니다.

SRS에서는 축소 관계 → $R$∗ ${\displaystyle {\overset {*}{\underset$ {$R}{\$rightarrow}}}가 모노이드 연산과 호환됩니다. ${\displaystyle x}$ → R$$∗ y${\$$displaystyle$ x{\overset ${*}{\$rightarrow}}y}는 모든 문자열 x, y, u, v ∈ σ {\displaystyle uxv{\overset {*}{\rightarrow}}uyv}에 대해 u v → R ∗ uxv {\underset {R}{\rightarrow}}uyv}를 의미합니다. 마찬가지로, \Sigma ^{*}에서 x,y,u,v\style x,y,u,v\를 ∗합니다. 마찬가지로, → R ${\displaystyle$ ${\underset$ {R$}{\rightarrow}}$의 반사형 전이 대칭 폐쇄,$$↔ R ∗ {\displaystyle {\overset {*}{\underset {R}{\leftrightarrow}}}는 일치이며, 이는 (정의상) 동등성 관계이며 문자열 연결과도 호환됩니다. 관계 ↔ $R$ ∗ {\$displaystyle$ ${\overset$ {*}{\$underset$ {$R}{\$leftrightarrow}}}는 R $displaystyle$ R}에 의해$생성$된 Thue 합동이라고 합니다. Thue 시스템에서$,$ $즉$ R ${\displaystyle$ R}이 대칭이면, ${\displaystyle \stackrel{}{\underset{}{}}}$ 쓰기 관계 → R ∗ ${\$$displaystyle$ ${\overset$ {*}{\$underset$ {$R}{\$rightarrow}}}이(가) Thue congrence ↔ R ∗ {\displaystyle {\overset {*}{\underset {R}{\rightarrow}}}과(와) 일치합니다.

반목계의 개념은 모노이드의 제시와 본질적으로 일치합니다. ↔ R ∗ {\${\displaystyle \stackrel{}{\underset{}{}}}$ {\$overset${*}{\$underset {R$}{\leftrightarrow$}}}$가 합동이므로, 우리는 자유 모노이드 σ ∗ {\displaystyle {\$mathcal$ {M}_{R}=\Sigma ^{*}/{\overset {\underset {R}{\rightarrow}}} {\displaystyle \Sigma ^{*}}의 인자 모노이드 ${\displaystyle {MR}_{}}$ = σ / ↔ R ∗ ${\$displaystyle {M$}$_{R}}를 Thue 합동으로 정의할 수 있습니다. If a monoid ${\displaystyle {\mathcal {M}}}$ is isomorphic with ${\displaystyle {\mathcal {M}}_{R}}$, then the semi-Thue system ${\displaystyle (\Sigma ,R)}$ is called a monoid presentation of ${\displaystyle {\mathcal {M}}}$.

우리는 즉시 다른 대수학 분야와 매우 유용한 연결을 얻습니다. 예를 들어$,$ 규칙 {${\displaystyle a}$ →${\displaystyle }$ε${\displaystyle ,}$ ${\displaystyle \mathrm{ba}}$ → ε }$$${\displaystyle \{a,b\}$ ${\$$displaystyle$ $\{ab$\rightarrow \varepsilon,ba\rightarrow \varepsilon \} {\${\displaystyle \mathrm{displaystyle}}$ \varepsilon }이(가) 빈 문자열인 ε $\{$a${\displaystyle ,b\}}$ {\displaystyle \varepsilon \}은 하나의 생성기에 있는 자유 그룹의 표현입니다. 대신 규칙이$${${\displaystyle a}$ b →$$ε } {\displaystyle \{ab\rightarrow \varepsilon \}}일 경우 이환 모노이드의 프레젠테이션을 얻습니다. 따라서 세미-Thue 시스템은 모노이드 및 그룹에 대한 단어 문제를 해결하기 위한 자연스러운 프레임워크를 구성합니다. 사실, 모든 모노이드는 ($$σ, R) ${\displaystyle$(\$Sigma$ R)} 형태의 표현을 가지고 있습니다. 즉, 항상 무한 알파벳을 통해 세미-Thue 시스템에 의해 표현될 수 있습니다.

일반적으로 반목 체계에 대한 단어 문제는 결정할 수 없습니다. 이 결과는 때때로 포스트-마르코프 정리로 알려져 있습니다.^[12]

용어 재작성 시스템

TRS(Term Rewriting System)는 객체가 용어인 재작성 시스템으로, 중첩된 하위 표현식이 있는 표현식입니다. 예를 들어 위의 § Logic 아래에 표시된 시스템은 용어 재작성 시스템입니다. 이 시스템의 항은$$$이진$ 연산자$($∨$)$ ${\displaystyle(\$vee${\displaystyle )\}}$및$$(∧) ${\displaystyle$(\wedge)}와${\displaystyle }$단항$연산자($¬$)$ {\displaystyle(\neg)}로 구성됩니다. 규칙에도 변수가 있습니다. 가능한 항을 나타냅니다(단, 하나의 변수는 항상 하나의 규칙 전체에서 동일한 항을 나타냅니다).

객체가 일련의 기호인 문자열 재작성 시스템과 대조적으로, 용어 재작성 시스템의 객체는 용어 대수를 형성합니다. 용어는 기호 트리로 시각화할 수 있으며, 허용된 기호 집합은 주어진 기호로 고정됩니다.

형식적 정의

재작성 규칙은 일반적으로 ${\displaystyle l}$ → r {\$displaystyle$ l$\rightarrow}$로 표시되는 한 쌍의 항으로$,$ 좌변 l이 우변 r로 대체될 수 있음을 나타냅니다. 용어 다시 쓰기 시스템은 그러한 규칙의 집합 R입니다. $규칙$ → ${\displaystyle r}$ {\$displaystyle$ l$\rightarrow}$은 왼쪽 항이 s의 일부 하위 항과 일치하는 경우 항에 적용할 수 있습니다. 즉, 어떤 위치 p에 뿌리를 둔 s {\displaystyle$$s}의 하위 항이 l이라는 용어에 대체 σ {\displaystyle \sigma }를 적용한 결과가 되도록 대체$$σ ${\displaystyle$ \sigma }이(가) 있는 경우. 규칙의 왼쪽과 일치하는 하위 용어를 redex 또는 reducible 표현식이라고 합니다.^[13] 그런 다음 이 규칙 적용의 결과 항 t는 위치 핀의 하위 항을 대체$$σ {\displaystyle$$\sigma}가 적용된 r ${\displaystyle$ r$}$로 대체한 결과입니다(그림 1 참조). In this case, ${\displaystyle s}$ is said to be rewritten in one step, or rewritten directly, to ${\displaystyle t}$ by the system ${\displaystyle R}$, formally denoted as ${\displaystyle s\rightarrow _{R}t}$, ${\displaystyle s{\underset {R}{\rightarrow }}t}$, 또는 $일부$ 작성자가 s → ${\displaystyle \stackrel{}{}}$ $displaystyle {\overset$ {$R} {\rightarrow}}t}$을(를) 표시합니다.

항 ${\displaystyle {t1}_{}}$ ${\displaystyle t_{1}}$을 여러 단계로 ${\displaystyle {다시}_{}}$ 쓸 수 있는 경우$,$ 즉, 항 t1 {\$displaystyle$ ${\displaystyle t\_}$${$${\displaystyle n}$$},$ $즉,$ ${\displaystyle {항}_{}}$ t1 → R ⋯ → R tn {\displaystyle t_{1}{\underset {R}{\rightarrow }}{\underset {R}{\rightarrow }}\cdots {\underset {R}{\rightarrow }}, $t$ ${\displaystyle 1_{}}$ ${\displaystyle t_{1}}$항은 ${\displaystyle \stackrel{}{\underset{}{}}}$ ${\displaystyle 1_{}}$ → R + t {\$displaystyle$t_${n}$로 공식적으로 ${\displaystyle {표시}_{}}$되는 t ${\displaystyle 1_{}}$ ${\displaystyle t_{1}{\overset {+}{\underset {R}{\rightarrow}}t_{n}}$로 다시 기록된다고 합니다$.$ 즉, 관계 → ${\displaystyle \stackrel{}{\underset{}{}}}$+ ${\displaystyle {\$overset {+}{\underset {R}{\rightarrow}}}는 관계 → R {\displaystyle {\underset {R}{\rightarrow}}; 종종, ${\displaystyle \stackrel{}{\underset{}{}}}$ → $R$$$∗ {\displaystyle {\$overset {*}{\underset$ {R}{\rightarrow}} 표기는 → R {\displaystyle {\underset {R} {\rightarrow}}의 반사-일시적 폐쇄를 나타내는 데 사용됩니다. 즉, ${\displaystyle s{\overset {*}{\underset {R}{\rightarrow }}}t}$ if ${\displaystyle s=t}$ or ${\displaystyle s{\overset {+}{\underset {R}{\rightarrow }}}t}$.^[14] A term rewriting given by a set ${\displaystyle R}$ of rules can be viewed as an abstract rewriting system as defined above, ${\displaystyle \underset{}{}}$를 개체로 사용하고 → R {\$displaystyle$ ${\underset {$R} ${\rightarrow}}$을(를) 다시 쓰기 관계로 사용합니다.

예를 들어 ${\displaystyle x}$∗${\displaystyle (}$y ∗ ${\displaystyle z}$)${\displaystyle }$→ (x ∗ $y)$∗ z ${\$displaystyle$$x*(y*z)\rightarrow(x*y)*z}는 일반적으로 {\displaystyle *} ∗의 연결에 대해 일반적인 형식을 설정하는 데 사용되는 재작성 규칙입니다. ${\displaystyle 이}$ 규칙은${\displaystyle }$∗$a$+${\displaystyle \frac{}{1}}$ ) ↦$(a$ + 2 ) $1$${\displaystyle \frac{}{}}$↦(2 ↦ $3$${\displaystyle$ {\frac {${\displaystyle \frac{\mathrm{a}}{}}$*(a+1)*($a+2$$)\}\{$$1*($2$*$3)} {\$displaystyle$ \{x\mapto a,\;y\mapto a+1,\;z\mapto a+2\}} {\displaystyle \{x\mapto a,\;${\displaystyle \frac{}{}}$\mapto a+${\displaystyle \frac{1}{}}$,\;z\mapto a+2\}}의 분자에 적용할 수 있습니다. 그림 2를 참조하십시오. ${\displaystyle \mathrm{규칙}}$의 ${\displaystyle \mathrm{오른쪽}}$에 이 치환을 적용하면$($∗$(a$ +${\displaystyle }$1)${\displaystyle }$∗(a + $2$)${\displaystyle($a$*($a + 1))*(a + 2)}이라는 용어가 나오고, 분자를 해당 용어로 대체하면 (a + 1) ∗(a + 2) ∗(2) ∗(3) {\displaystyle {(a*(a + 1)*(a + 2)}{1*(2*3)}, 다시 쓰기 규칙을 적용한 결과 용어입니다. 전체적으로 재작성 규칙을 적용하면 $기본$ 대수학에서 ${\$${\displaystyle \frac{displaystyle}{}}$*} ∗에$대한$ 연관성 법칙을 적용하는 것((a + 1 ) ∗(a + 2 ) 1 ∗(2 ∗ 3) {\displaystyle {\frac {a*(a+1)*(a+2)}{1*(2*3)}}"이 달성됩니다. ${\displaystyle \frac{\mathrm{또는}}{}}$ 원래 항의 분모에 ${\displaystyle \frac{\mathrm{규칙}}{}}$을 적용하여${\displaystyle \frac{}{}}$∗${\displaystyle \frac{\mathrm{a}}{}}$+ ${\displaystyle \frac{1}{}}$) ∗$a$+ 2 ))(1 ∗ 2) ∗ 3 {\displaystyle {\frac {a*((a+1)*(a+2)}{(1*2)*3}}을(1*2)} 생성할 수 있습니다.

종료

일반적으로 재작성 시스템의 종료 문제는 추상 재작성 시스템#에서 처리됩니다.종결과 수렴. 특히 용어 재작성 시스템의 경우 다음과 같은 추가적인 미묘함을 고려해야 합니다.

좌변이 직선인 하나의 규칙으로 구성된 시스템의 종료도 결정할 수 없습니다.^[15][16] 단함수 기호만을 사용하는 시스템의 경우에도 종료는 결정할 수 없지만 유한 접지 시스템의 경우에는 결정할 수 있습니다.^[17]

다음 용어 재작성 시스템이 정규화되고 ^{[note 3]}있지만 종료되지 않으며,^{[note 4]} 통합되지 않습니다.^[18]

용어 재작성 시스템을 종료하는 다음 두 가지 예는 Toyama 때문입니다.^[19]

${\displaystyle f(0,1,x)\rightarrow f(x,x,x)}$

그리고.

${\displaystyle g(x,y)\rightarrow x,}$

${\displaystyle g(x,y)\rightarrow.}$

그들의 조합은 비종단적인 시스템입니다, 그 이후로.

이 결과는 더쇼비츠의 추측을 반증합니다.^[20] $누가{\displaystyle {}_{}}$, ${\displaystyle {R1\mathrm{}}_{}}${\$displaystyle$ $R_{1$$}},$ ${\displaystyle {R2\mathrm{}}_{}}${\$displaystyle R_{2}}$의 $좌변$과 ${\displaystyle {R2\mathrm{}}_{}}${\$displaystyle R_{2}$의 우변이 모두 직선인 경우, 두 개의 종결항 재작성 $시스템$의 결합이 다시 종결된다고$$ 주장하였는바, $그리고{\displaystyle {}_{}}$ R ${\displaystyle {1\mathrm{}}_{}}$ ${\$의 좌변과 $R{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$의 우변 사이에는 "오버랩"이 없습니다$.$ 이 모든 특성은 토야마의 예에 의해 만족됩니다.

용어 재작성 시스템에 대한 종료 증명에 사용되는 관계 순서 지정은 순서 재작성 및 경로 순서 지정(용어 재작성)을 참조하십시오.

고차 개서 시스템

고차 재작성 시스템은 1차 항 재작성 시스템을 람다 항으로 일반화하여 고차 함수 및 바인딩 변수를 허용합니다.^[21] 1차 TRS에 대한 다양한 결과는 HRS에 대해서도 재구성될 수 있습니다.^[22]

그래프 다시 쓰기 시스템

그래프 재작성 시스템은 용어 재작성 시스템의 또 다른 일반화로, (그라운드-) 용어 대신 그래프 / 해당 트리 표현에서 작동합니다.

트레이스 개서 시스템

추적 이론은 추적 모노이드 및 이력 모노이드를 통해 보다 공식적인 용어로 다중 처리를 논의할 수 있는 수단을 제공합니다. 트레이스 시스템에서도 다시 쓰기를 수행할 수 있습니다.

철학

시스템을 다시 쓰는 것은 인과 관계의 목록에서 최종 효과를 추론하는 프로그램으로 볼 수 있습니다. 이렇게 시스템을 다시 쓰는 것은 자동화된 인과성 증명이라고 볼 수 있습니다.^{[citation needed]}

참고 항목

• 임계쌍(논리)
• 컴파일러
• 크누스-벤딕스 완성 알고리즘
• L-시스템은 병렬로 수행되는 재작성을 지정합니다.
• 컴퓨터 과학의 참조 투명성
• 규정 개서
• 로 미적분학
• 인터랙션 네트

메모들

더보기

• Baader, Franz; Nipkow, Tobias (1999). Term rewriting and all that. Cambridge University Press. ISBN 978-0-521-77920-3. 316쪽.
• Marc Bezem, Jan Willem Klop, Roel de Vrijer ("Terese"), Term Rewriting Systems ("TereSe"), Cambridge University Press, 2003, ISBN 0-521-39115-6. 가장 최근의 종합 모노그래프입니다. 그러나 아직 표준이 아닌 주석과 정의를 공정하게 사용합니다. 예를 들어 Church-Rosser 속성은 합류점과 동일한 것으로 정의됩니다.
• Nachum Dershowitz and Jean-Pierre Jouannaud "다시 쓰는 시스템", Jan van Leeuwen (Ed.) 제6장, 이론 컴퓨터 과학 핸드북, B권: 형식적 모델과 의미론. Elsevier and MIT Press, 1990, ISBN 0-444-88074-7, 페이지 243–320. 이 장의 사전 인쇄는 저자가 자유롭게 사용할 수 있지만 수치가 누락되어 있습니다.
• 나첨 더쇼비츠와 데이비드 플래리스트. "다시 쓰기", 존 앨런 로빈슨과 안드레이 보론코프 9장, 자동 추론 핸드북, 1권.
• Gerard Huet et Derek Oppen, 방정식과 재작성 규칙, A Survey (1980) Stanford 검증 그룹, 보고서 N° 15 컴퓨터 과학부 보고서 N° STAN-CS-80-785
• 얀 윌렘 클롭. "용어 다시 쓰기 시스템", 샘슨 에이브람스키 1장, 도브 M. 가베이와 톰 마이바움(Eds.), 컴퓨터 과학 논리학 핸드북, 2권: 배경: 계산 구조.
• David Plaist. Dov M. Gabbay, C. J. Hogger와 John Alan Robinson (Eds.), 인공 지능과 논리 프로그래밍의 논리학 핸드북, 1권.
• 위르겐 아벤하우스와 클라우스 마들렌. "용어 다시 쓰기와 등식적 추론". Ranan B에서. 바네르지(Ed.), 인공지능의 공식 기법: A Source book, Elsevier (1990).

문자열 다시 쓰기

• 로널드 5세. 책과 프리드리히 오토, 스트링 리라이팅 시스템, 스프링어(1993).
• 벤저민 베닝호펜, 수잔 켐메리치, 마이클 M. 리히터, 축소 시스템. LNCS 277, Springer-Verlag (1987).

다른.

• 마틴 데이비스, 론 시걸, 일레인 J. Weyuker, (1994) 계산 가능성, 복잡성 및 언어: 이론 컴퓨터 과학의 기초 – 제2판, 학술 출판부, ISBN 0-12-206382-1

외부 링크

• 다시 쓰기 홈 페이지
• IFIP 워킹 그룹 1.6
• 인스브루크 대학교 아트 미드델도프의 개작 연구자들
• 종료 포털
• 모드 시스템 — 일반적인 용어 다시 쓰기 시스템의 소프트웨어 구현입니다.^[5]

참고문헌