추상 재작성 시스템

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 기본 개념
4. 처치-로서 속성(Church-Rosser Property)과 합류성(Confluence)
5. 종료성(Termination)과 수렴성(Convergence)
참조

1. 개요

추상 재작성 시스템(ARS)은 객체 집합과 객체를 변환하는 규칙으로 구성된다. ARS는 객체 집합과 이항 관계인 감축 관계로 이루어지며, 감축, 재작성 또는 감축 관계라고 불린다. ARS는 상태 전이 시스템과 유사하지만, 객체의 변환에 초점을 맞춘다. 핵심 개념으로는 추이적 폐포, 반사적 추이적 폐포, 대칭 폐포 등이 있으며, 정규형, 결합성과 같은 개념도 포함한다. ARS는 처치-로서 속성, 합류성, 반합류성, 국소 합류성 등의 속성을 가질 수 있으며, 종료성과 수렴성 또한 중요한 특성이다. 뉴먼의 보조정리는 종료 ARS가 국소 합류적일 경우에만 합류적임을 보여준다.

2. 정의

'''추상 재작성 시스템'''(Abstract Rewriting System, ARS)은 객체 집합 ''A''와 ''A'' 위의 이항 관계 → 로 구성된다. 이 관계는 '''재작성 관계''',^[1] '''감축 관계''', 또는 단순히 '''감축'''이라고 불린다.^[3] 이 관계는 객체들이 어떻게 변환될 수 있는지를 나타낸다.

어떤 경우에는 규칙의 일부를 구분하는 것이 유용하다. 예를 들어, 전체 감축 관계는 결합 법칙과 교환 법칙 규칙으로 구성될 수 있다. 그래서 일부 저자들은 감축 관계 →를 여러 관계의 합집합으로 정의하기도 한다. 예를 들어 ${\rightarrow_1 \cup \rightarrow_2} = {\rightarrow}$ 인 경우 (A, →₁, →₂) 로 표기한다.

ARS는 수학적으로 레이블이 없는 상태 전이 시스템과 같다. 관계가 여러 개의 합집합으로 표현될 때는 레이블이 있는 상태 전이 시스템과 같다. 그러나 연구의 초점과 용어는 다르다. 상태 전이 시스템에서는 레이블을 동작으로 해석하는 데 관심이 있지만, ARS에서는 객체가 어떻게 다른 객체로 변환(재작성)될 수 있는지에 초점을 맞춘다.^[4]

예를 들어 객체 집합이 ''T'' = {''a'', ''b'', ''c''}이고, 이항 관계가 ''a'' → ''b'', ''b'' → ''a'', ''a'' → ''c'', ''b'' → ''c''로 주어졌다고 하자. ''a''와 ''b'' 모두 ''c''로 변환될 수 있다. 그리고 ''c''는 더 이상 변환될 수 없다.

3. 기본 개념

추상 재작성 시스템(ARS)은 객체 집합과 이를 변환하는 규칙을 지정하는 가장 일반적인 개념이다. 최근에는 "추상 재작성 시스템"이라는 용어를 사용하기도 한다.^[2] ("재작성" 대신 "감축"이라는 단어를 선호하는 경우도 있지만, 이는 ARS의 특수한 경우인 시스템의 이름에 "재작성"을 일관되게 사용하는 것과는 다르다.)^[3]

ARS는 일반적으로 객체라고 불리는 요소로 이루어진 집합 ''A''와, ''A''에 대한 이항 관계인 →로 표기되는 '''감축 관계''', '''재작성 관계'''^[1] 또는 단순히 '''감축'''으로 구성된다.^[3] "감축"이라는 용어는 이 관계가 반드시 객체의 어떤 척도를 줄이는 것은 아니기 때문에 다소 오해의 소지가 있다.

일부 맥락에서는 감축 관계 →의 일부 하위 집합을 구분하는 것이 유용할 수 있다. 예를 들어 전체 감축 관계는 결합 법칙 및 교환 법칙 규칙으로 구성될 수 있다. 결과적으로 일부 저자는 감축 관계 →를 ${\rightarrow_1 \cup \rightarrow_2} = {\rightarrow}$ 와 같이 일부 관계의 인덱싱된 합집합으로 정의하기도 한다.

ARS는 수학적 객체로서 레이블이 없는 상태 전이 시스템과 정확히 동일하며, 관계가 인덱싱된 합집합으로 간주되는 경우 레이블이 지정된 상태 전이 시스템과 동일하다. 그러나 상태 전이 시스템에서는 레이블을 동작으로 해석하는 데 관심이 있는 반면, ARS에서는 객체가 어떻게 다른 객체로 변환(재작성)될 수 있는지에 초점을 맞춘다는 차이점이 있다.^[4]

3. 1. 관계 표기법

몇 가지 기본적인 개념과 표기법을 먼저 정의한다.^[5]

$\stackrel{+}{\rightarrow}$ 는 $\rightarrow$ 의 추이적 폐포이다.
$\stackrel{*}{\rightarrow}$ 는 $\rightarrow$ 의 반사적 추이적 폐포이다. 즉, $(\rightarrow) \cup (=)$ 의 추이적 폐포이며, 여기서 =는 항등 관계이다. 동일하게, $\stackrel{*}{\rightarrow}$ 는 $\rightarrow$ 을 포함하는 가장 작은 전순서이다.
마찬가지로, $\stackrel{+}{\leftarrow}$ 과 $\stackrel{*}{\leftarrow}$ 는 ${\leftarrow}$ 의 폐포이며, ${\rightarrow}$ 의 역관계이다.
$\leftrightarrow$ 는 $\rightarrow$ 의 대칭 폐포이며, 이는 $\rightarrow$ 와 ${\leftarrow}$ 의 합집합이다.
$\stackrel{*}{\leftrightarrow}$ 는 $\rightarrow$ 의 반사적 추이적 대칭 폐포이다. 즉, $(\leftrightarrow) \cup (=)$ 의 추이적 폐포이다. 동일하게, $\stackrel{*}{\leftrightarrow}$ 는 $\rightarrow$ 를 포함하는 가장 작은 동치 관계이다.

3. 2. 정규형

''A''의 객체 ''x''가 다른 ''A''의 ''y''가 존재하고

x \rightarrow y

이면 ''환원 가능''이라고 부르고, 그렇지 않으면 ''환원 불가능'' 또는 '''정규형'''이라고 부른다. 객체 ''y''가

x \stackrel{*}{\rightarrow} y

이고 ''y''가 환원 불가능하면 ''x''의 정규형이라고 한다. ''x''가 ''유일한'' 정규형을 가지면 보통

x\downarrow

로 표기한다. 객체 집합 ''T'' = {''a'', ''b'', ''c''}이고, 이진 관계 규칙이 ''a'' → ''b'', ''b'' → ''a'', ''a'' → ''c'', ''b'' → ''c''로 주어지는 예시에서, ''c''는 정규형이며

c = a\downarrow = b\downarrow

이다. 모든 객체가 적어도 하나의 정규형을 가지면 ARS는 ''정규화''라고 부른다.

3. 3. 결합성

두 객체 ''x''와 ''y''에 대해,

x \stackrel{*}{\rightarrow} z \stackrel{*}{\leftarrow} y

의 속성을 가진 ''z''가 존재할 경우, ''x''와 ''y''는 결합 가능하다고 한다. 이 정의로부터 결합 가능성 관계를

\stackrel{*}{\rightarrow} \circ \stackrel{*}{\leftarrow}

로 정의할 수 있으며, 여기서

\circ

는 관계의 합성이다. 결합 가능성은 일반적으로

\downarrow

로 표시되며, ''x''와 ''y''가 결합 가능한 경우

x\mathbin\downarrow y

라고 쓴다.

4. 처치-로서 속성(Church-Rosser Property)과 합류성(Confluence)

추상 재작성 시스템(ARS)은 처치-로서 속성과 합류성이라는 중요한 성질을 갖는다.

ARS $(A,\rightarrow)$ 에서,

'''합류성'''은 ''A''의 모든 ''w'', ''x'', ''y''에 대해 $x \stackrel{*}{\leftarrow} w \stackrel{*}{\rightarrow} y$ 가 $x\mathbin\downarrow y$ 를 함의하는 경우이다.
'''반합류성'''은 ''A''의 모든 ''w'', ''x'', ''y''에 대해 $x \leftarrow w \stackrel{*}{\rightarrow} y$ 가 $x\mathbin\downarrow y$ 를 함의하는 경우이다.
'''국소 합류성'''은 ''A''의 모든 ''w'', ''x'', ''y''에 대해 $x \leftarrow w \rightarrow y$ 가 $x\mathbin\downarrow y$ 를 함의하는 경우이다. 국소 합류성은 '''약한 합류성'''이라고도 불린다.

국소 합류성은 다른 합류성 개념들과 동등하지 않으며, 합류성보다 엄격하게 약하다. 예를 들어,

\{b\rightarrow c, c\rightarrow b, b\rightarrow a, c\rightarrow d\}

는 국소 합류적이지만 합류적이지 않다(그림 참조).

문헌에 따라 정의에 차이가 있을 수 있다. 테레세(Terese)에서는 처치-로서 속성과 합류성이 동의어로 사용되며, 이 글에서의 합류성 정의와 동일하다. 이 글에서 정의된 처치-로서는 다른 이름으로 불리지만 동등한 속성으로 제시된다.^[10]

4. 1. 처치-로서 속성

ARS는 모든 객체 ''x'', ''y''에 대해

x \stackrel{*}{\leftrightarrow} y

가

x\mathbin\downarrow y

를 함의할 경우 ''처치-로서 속성''(Church–Rosser 속성)을 가진다고 한다. 이는 서로 다르게 재작성된 두 객체가 결국에는 같은 형태로 결합될 수 있음을 의미한다. 앨론조 처치와 J. 바클리 로서는 1936년에 람다 계산법이 이 속성을 갖는다는 것을 증명했고,^[6] 따라서 이 속성의 이름이 유래되었다.^[7] 처치-로서 속성을 가진 ARS에서 단어 문제는 공통 후계자를 찾는 문제로 축소될 수 있다. 처치-로서 시스템에서 객체는 ''최대 하나''의 정규 형식을 갖는다. 즉, 객체의 정규 형식은 존재한다면 유일하지만, 존재하지 않을 수도 있다.

'''정리.''' ARS에 대해 다음 세 가지 조건은 동등하다.

(i) 처치-로서 속성을 갖는다.
(ii) 합류적이다.
(iii) 반합류적이다.^[8]

'''따름 정리'''.^[9] 합류적 ARS에서

x \stackrel{*}{\leftrightarrow} y

이면

''x''와 ''y''가 모두 정규 형식인 경우, ''x'' = ''y''이다.
''y''가 정규 형식인 경우, $x \stackrel{*}{\rightarrow} y$ 이다.

4. 2. 합류성

추상 재작성 시스템(ARS)

(A, \rightarrow)

는 ''A''의 모든 ''w'', ''x'', ''y''에 대해

x \stackrel{*}{\leftarrow} w \stackrel{*}{\rightarrow} y

이면

x\mathbin\downarrow y

인 경우 ''합류적''이라고 한다.^[8] 즉, 어떤 경로가 공통 조상(''w'')으로부터 분기되더라도, 그 경로가 ''어떤'' 공통 후계자에서 결합된다는 것을 의미한다. 이 개념은 특정 객체 ''w''의 속성으로 세분화될 수 있으며, 모든 요소가 합류적인 시스템을 합류적이라고 부른다.

'''정리.''' ARS에 대해 다음 세 가지 조건은 동등하다: (i) Church–Rosser 속성을 갖는다, (ii) 합류적이다, (iii) 반합류적이다.^[8]

'''따름 정리'''.^[9] 합류적 ARS에서

x \stackrel{*}{\leftrightarrow} y

이면

''x''와 ''y''가 모두 정규 형식인 경우, ''x'' = ''y''이다.
''y''가 정규 형식인 경우, $x \stackrel{*}{\rightarrow} y$ 이다.

문헌에 따라 정의에 차이가 있을 수 있다. 테레세(Terese)에서는 Church–Rosser 속성과 합류성이 동의어로 사용되며, 이 글에서의 합류성 정의와 동일하다. 이 글에서 정의된 Church–Rosser는 다른 이름으로 불리지만 동등한 속성으로 제시된다. 이러한 차이는 의도적인 것이다.^[10] 위의 따름 정리에 따라 정규 형식 ''y''는

x \stackrel{*}{\leftrightarrow} y

속성을 가진 기약 불가능한 ''y''로 정의될 수 있다. Book과 Otto에서 사용된 이 정의는 합류적 시스템에서는 이 글의 정의와 동일하지만, 비합류적 ARS에서는 더 포괄적이다.

4. 2. 1. 반합류성

추상 재작성 시스템(ARS)에서, ''A''의 모든 ''w'', ''x'', ''y''에 대해

x \leftarrow w \stackrel{*}{\rightarrow} y

가

x\mathbin\downarrow y

를 함의하는 경우 ''반합류적''이라고 한다. 이는 ''w''에서 ''x''로의 단일 단계 감소로 인해 합류성과 다르다.^[8]

4. 2. 2. 국소 합류성

국소 합류성은 ''A''의 모든 ''w'', ''x'', ''y''에 대해

x \leftarrow w \rightarrow y

가

x\mathbin\downarrow y

를 함의하는 경우이다. 이 속성은 때때로 '''약한 합류성'''이라고도 불린다.^[8]

반면에 국소 합류성은 이 섹션에 주어진 다른 합류성의 개념과 동등하지 않지만, 합류성보다 엄격하게 약하다. 전형적인 반례는

\{b\rightarrow c, c\rightarrow b, b\rightarrow a, c\rightarrow d\}

인데, 이는 국소 합류적이지만 합류적이지 않다(그림 참조).

4. 3. 정리 및 따름 정리

앨론조 처치와 J. 바클리 로서는 1936년에 람다 계산법이 처치-로서 속성을 갖는다는 것을 증명했으며,^[6] 이 속성의 이름은 여기에서 유래되었다.^[7]

'''정리.''' 추상 재작성 시스템(ARS)에 대해 다음 세 가지 조건은 동등하다. (i) 처치-로서(Church–Rosser) 속성을 갖는다, (ii) 합류적이다, (iii) 반합류적이다.^[8]

'''따름 정리'''.^[9] 합류적 ARS에서

x \stackrel{*}{\leftrightarrow} y

이면

''x''와 ''y''가 모두 정규 형식인 경우, ''x'' = ''y''이다.
''y''가 정규 형식인 경우, $x \stackrel{*}{\rightarrow} y$ 이다.

5. 종료성(Termination)과 수렴성(Convergence)

추상 재작성 시스템(ARS)은 무한 체인 $x_0 \rightarrow x_1 \rightarrow x_2 \rightarrow \cdots$ 가 없을 경우 '''종료''' 또는 ''네터리안''이라고 한다.^[11] 이는 재작성 관계가 네터리안 관계임을 나타낸다. 종료 ARS에서는 모든 객체가 적어도 하나의 정규형을 가지므로 정규화된다. 역은 성립하지 않는다. 예를 들어, $a \rightarrow b \rightarrow a \rightarrow b \rightarrow \cdots$ 와 같은 무한 재작성 체인이 있을 수 있다. 합류적이고 종료되는 ARS를 '''정규'''^[11] 또는 '''수렴'''이라고 한다. 수렴 ARS에서 모든 객체는 고유한 정규형을 갖는다.

'''정리''' (뉴먼의 보조정리): 종료 ARS는 국소적으로 합류적일 경우에만 합류적이다.

뉴먼이 1942년에 이 결과에 대한 원래 증명을 발표하였고, 1980년에 휘트(Huet)가 잘 정렬된 귀납법을 적용하여 더 간단한 증명을 발표했다.^[12]

5. 1. 종료성

추상 재작성 시스템에서 무한 체인

x_0 \rightarrow x_1 \rightarrow x_2 \rightarrow \cdots

가 존재하지 않으면, '''종료''' 또는 ''네터리안''이라고 부른다. (이는 재작성 관계가 네터리안 관계임을 의미한다.) 종료되는 추상 재작성 시스템(ARS)에서는 모든 객체가 적어도 하나의 정규형을 가지므로 정규화된다. 그러나 그 역은 성립하지 않는다. 예를 들어,

a \rightarrow b \rightarrow a \rightarrow b \rightarrow \cdots

와 같이 무한히 재작성되는 체인이 있을 수 있다. 합류성과 종료성을 모두 만족하는 ARS는 '''정규'''^[11] 또는 '''수렴'''이라고 한다. 수렴 ARS에서 모든 객체는 고유한 정규형을 가진다.

'''정리''' (뉴먼의 보조정리): 종료 ARS는 국소적으로 합류적일 때에만 합류적이다.

1942년 뉴먼이 이 정리에 대한 최초 증명을 발표했지만, 다소 복잡했다. 이후 1980년, Huet이

\rightarrow

이 종료될 때 잘 정렬된 귀납법을 적용하여 훨씬 간결한 증명을 제시했다.^[12]

5. 2. 수렴성

합류적이고 종료되는 추상 재작성 시스템(ARS)을 '''정규'''^[11] 또는 '''수렴'''이라고 한다. 수렴 ARS에서 모든 객체는 고유한 정규형을 갖는다. 그러나 예시 1에서 볼 수 있듯이, 모든 요소에 대해 고유한 정규형이 존재하려면 시스템이 합류적이고 정규화되는 것으로 충분하다.

'''정리''' (뉴먼의 보조정리): 종료 ARS는 국소적으로 합류적일 경우에만 합류적이다.

뉴먼이 1942년에 이 결과에 대한 원래 증명은 다소 복잡했다. 1980년에 휘트(Huet)가

\rightarrow

이 종료될 때 잘 정렬된 귀납법을 적용할 수 있다는 사실을 이용하여 훨씬 더 간단한 증명을 발표했다.^[12]

5. 3. 뉴먼의 보조정리 (Newman's Lemma)

'''정리''' (뉴먼의 보조정리): 종료되는 ARS는 국소적으로 합류적일 경우에만 합류적이다.^[11]

1942년 뉴먼이 처음 증명했을 때는 다소 복잡했으나, 1980년 Huet이

\rightarrow

이 종료될 때 잘 정렬된 귀납법을 적용할 수 있다는 사실을 이용하여 훨씬 더 간단한 증명을 발표했다.^[12]

참조

_[1] 서적
_[2] 서적
_[3] 서적
_[4] 서적
_[5] 서적
_[6] 서적
_[7] 서적
_[8] 서적
_[9] 서적
_[10] 서적
_[11] 서적
_[12] 서적
_[13] 서적

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com