추상적 재작성 시스템

수학적 논리학 및 이론 컴퓨터학에서 추상적 재쓰기 시스템(추상적) 또는 추상적 재쓰기 시스템, 약칭 ARS)은 재쓰기 시스템의 본질적 개념과 속성을 포착한 형식주의다.가장 간단한 형태에서 ARS는 전통적으로 → $\rightarrow$ 로 표시된 이진 관계와 함께 단순한 집합("개체")이다 $\rightarrow$ 이 정의는 우리가 이진 관계의 부분 집합을 색인화(라벨)하면 더욱 정교해질 수 있다.ARS는 단순함에도 불구하고 정상 형태, 종료 및 다양한 혼합 개념과 같은 재쓰기 시스템의 중요한 속성을 설명하기에 충분하다.

역사적으로, 추상적인 환경으로 다시 쓰는 형식화는 여러 번 있었는데, 각각은 그 특색을 가지고 있다.이는 일부 개념이 동등하다는 사실에 기인한다(이 글의 아래 참조).모노그래프나 교과서에서 가장 흔히 접하고, 여기서 일반적으로 따르게 되는 형식화는 제라드 휴에(1980년) 때문이다.^[1]

정의

추상적 감소 시스템(ARS)은 개체와 규칙을 변환하기 위해 적용할 수 있는 일련의 규칙을 지정하는 것에 대한 가장 일반적인 (단차원적) 개념이다.보다 최근에는 작가들도 추상적 재작성 시스템이라는 용어를 사용하고 있다.(^[2]재작성 대신 여기서 축소라는 단어를 선호하는 것은 ARS를 특정하는 시스템 이름에 있어서 획일적인 "재작성"의 사용에서 벗어나는 것에 해당한다.보다 전문화된 시스템의 이름에는 '축소'라는 단어가 등장하지 않기 때문에 오래된 텍스트 축소 시스템에서는 ARS와 동의어가 된다.^[3]

ARS는 일반적으로 A에 대한 이항관계와 함께 원소를 객체라고 하는 집합 A로, 전통적으로 →에 의해 표시되며, 감소관계라고 하는 것을 Reducation relarge^[2] relation 또는 just redract라고 한다.^[3]"축소"를 사용하는 이 (기존) 용어는 약간 오해의 소지가 있다. 왜냐하면 그 관계가 반드시 물체의 일부 측정치를 감소시키는 것은 아니기 때문이다.

어떤 맥락에서 규칙의 일부 하위 집합(즉, 감소 관계의 일부 하위 집합 → 예: 전체 감소 관계는 연관성과 공통성 규칙으로 구성될 수 있음)을 구별하는 것이 유익할 수 있다.따라서 일부 저자들은 감소 관계를 정의한다. ${\rightarrow _{1}\cup \rightarrow _{2}}={\rightarrow }$ 를 들어 ${\rightarrow _{1}\cup \rightarrow _{2}}={\rightarrow }$ → ${\rightarrow _{1}\cup \rightarrow _{2}}={\rightarrow }$ for → ${\rightarrow _{1}\cup \rightarrow _{2}}={\rightarrow }$ 2 ${\rightarrow _{1}\cup \rightarrow _{2}}={\rightarrow }$ = ${\rightarrow _{1}\cup \rightarrow _{2}}={\rightarrow }$ → ${\$ ${\rightarrow _{1}\cup \rightarrow _{2}}={\rightarrow }$ 사용된 표기법은 (A, →,₁ →, →, →)이다.₂

수학적 객체로서 ARS는 라벨이 부착되지 않은 상태 전환 시스템과 정확히 동일하며, 관계를 지수 결합으로 간주한다면 ARS는 라벨이 부착된 상태 전환 시스템과 동일하다.그러나 연구의 초점과 용어는 다르다.주 전환 시스템에서 라벨을 동작으로 해석하는 데 관심이 있는 반면, ARS에서는 물체가 다른 물체로 어떻게 변환(재작성)될 수 있는지에 초점을 맞춘다.^[4]

예 1

개체 집합이 T = {a, b, c}이고 규칙 a → b → a → a, a → c, b → c에 의해 이진 관계가 주어진다고 가정하자. 이러한 규칙은 a와 b 모두에 적용되어 c를 얻을 수 있음을 관찰하라.더욱이 c를 더 이상 변형시키기 위해서는 아무것도 적용할 수 없다.그러한 재산은 분명히 중요한 재산이다.

기본 개념

먼저 몇 가지 기본 개념과 관념을 정의하십시오.^[5]

${\stackrel {+}{\rightarrow }}$ + ${\$ 의 ${\stackrel {+}{\rightarrow }}$ transitive closure → $displaysty \rightarrow }.$
$【\$ $wrightarrow$ $\rightarrow$ 의 반사적 전이 폐쇄로 ${\stackrel {*}{\rightarrow }}$ $\rightarrow$ 즉 ( $(\rightarrow )\cup (=)$ → $(\rightarrow )\cup (=)$ ) $(\rightarrow )\cup (=)$ ( $(\rightarrow )\cup (=)$ = ) ${$ ( $(\rightarrow )\cup (=)$ ) {\ $displaystyle (\rightarrow )\cup (=)}$ 의 전이 폐쇄로 $(\rightarrow )\cup (=)$ 여기서 = ID 관계.동등하게 → $∗{\$ $rightarrow }}}}$ 은 ${\stackrel {*}{\rightarrow }}$ (는) 포함된 최소 사전 주문이다 $\rightarrow$
$£{\$ $displaystyle$ $\$ $좌우타로우$ $\leftrightarrow$ $}$ 의 대칭적 폐쇄 $\rightarrow$ 즉 $(\rightarrow )\cup (\rightarrow )^{-1}$ ( $(\rightarrow )\cup (\rightarrow )^{-1}$ → $(\rightarrow )\cup (\rightarrow )^{-1}$ ) $(\rightarrow )\cup (\rightarrow )^{-1}$ - $(\rightarrow )\cup (\rightarrow )^{-1}$ ${\$ 화살표 $)\컵(\오른쪽$ 화살표 $)^{-1}$ 즉, 관계 $(\rightarrow )\cup (\rightarrow )^{-1}$ → 역관계와의 결합이다 $\leftrightarrow$ .
${\stackrel {*}{\leftrightarrow }}$ is the reflexive transitive symmetric closure of $\rightarrow$ , i.e. the transitive closure of $(\leftrightarrow )\cup (=)$ . Equivalently, ${\stackrel {*}{\leftrightarrow }}$ is the $\rightarrow$ $\rightarrow$ 을(를) 포함하는 최소 동등성 관계 $\rightarrow$

정상형식

A에 있는 물체 x는 A와 x $x\rightarrow y$ → $x\rightarrow y$ 에 다른 y가 있을 경우 환원 $가능$ 으로 불리며 $x\rightarrow y$ 그렇지 않을 경우 $x\rightarrow y$ unreducable $또는$ 정상적인 형태라고 불린다.개체 y는 $x{\stackrel {*}{\rightarrow }}y$ → $x{\stackrel {*}{\rightarrow }}y$ y ${\displaystyle x{\stackrel {*}{\\rightarrow }}y$ y는 rereduccessible이 불가능하다면 보통 형태의 x라고 한다.x가 고유한 정상적인 형태를 가지고 있다면, 이것은 보통 $x\downarrow$ $x\downarrow$ ${\displaystyle$ x $\downarrow }$ 로 표시된다 $x\downarrow$ 위의 예 1에서 $c=a\downarrow =b\downarrow$ 는 $c=a\downarrow =b\downarrow$ $c=a\downarrow =b\downarrow$ ${\displaysty c=a\downarrow =b\downarrow$ $c=a\downarrow =b\downarrow$ 만약 모든 물체가 적어도 하나의 정상적인 형태를 가지고 있다면 ARS를 정상화라고 한다.

결합성

정상 형태의 존재에 비해 관련되지만 약한 개념은 결합 가능한 두 개체의 개념이다: x와 y는 $x{\stackrel {*}{\rightarrow }}z{\stackrel {*}{\leftarrow }}y$ → $x{\stackrel {*}{\rightarrow }}z{\stackrel {*}{\leftarrow }}y$ z $x{\stackrel {*}{\rightarrow }}z{\stackrel {*}{\leftarrow }}y$ $x{\stackrel {*}{\rightarrow }}z{\stackrel {*}{\leftarrow }}y$ y {\ $displaystyle$ ${\stackrel {*}{\rightarrow$ } $z{\stackrel{*}{\좌측$ 화살표 $x{\stackrel {*}{\rightarrow }}z{\stackrel {*}{\leftarrow }}y$ 이 정의에서 분명히 하나의 개체가 될 수 있다.e → ${\stackrel {*}{\rightarrow }}\circ {\stackrel {*}{\leftarrow }}$ $\circ$ ${\stackrel {*}{\rightarrow }}\circ {\stackrel {*}{\leftarrow }}$ ${\stackrel {*}{\rightarrow }}\circ {\stackrel {*}{\leftarrow }}$ ${$ {\ $displaystyle {\stackrel {*}{\wrightarrow }}\\stackrel {*}{\$ $displaystyle \circ}}}}}}$ 의 가입성 관계 구성 $\circ$ $.$ 조인성은 일반적으로 $\downarrow$ ${\displaystyle \downarrow$ $\downarrow$ 과(와) 함께 다소 혼란스럽게 표시되지만, 이 표기법에서 아래쪽 화살표는 이진 관계, 즉 x와 y가 조인 가능한 경우 $x{\mathbin {\downarrow }}y$ $x{\mathbin {\downarrow }}y$ $x{\mathbin {\downarrow }}y$ $x{\mathbin {\downarrow }}y$ $x{\mathbin {\downarrow }y$ 라고 쓴다.

교회-로스터의 재산과 결합 개념

An ARS is said to possess the Church-Rosser property if and only if $x{\stackrel {*}{\leftrightarrow }}y$ implies $x{\mathbin {\downarrow }}y$ for all objects x, y. Equivalently, the Church-Rosser property means that the reflexive transitive symmetric closure is contained in the 가입성 관계알론조 교회와 J. 바클리 로서는 1936년에 람다 미적분학이 이 속성을 가지고 있다는 것을 증명했다.^[6] 따라서 그 재산의 이름은 다음과 같다.^[7]Church-Rosser 재산과 함께 ARS에서는 단어 문제가 공통의 후계자를 찾는 것으로 축소될 수 있다.Church-Roser 시스템에서, 물체는 적어도 하나의 정상적인 형태를 가지고 있다; 그것은 물체의 정상적인 형태가 존재한다면 독특하지만, 그것은 존재할 수 없을지도 모른다.

Church-Rosser보다 간단한 다양한 성질은 그것과 동등하다.이러한 동등한 성질의 존재는 어떤 시스템이 덜 일하면서 Church-Rosser라는 것을 증명할 수 있게 해준다.게다가, 결합의 개념은 Church-Roser에게는 불가능한 어떤 특정한 물체의 속성으로 정의될 수 있다.ARS $(A,\rightarrow )$ , $(A,\rightarrow )$ → $(A,\rightarrow )$ ) ${\displaystyle(A,\오른쪽$ 화살표 $)}$ 은(는) 다음과 같은 것으로 알려져 $(A,\rightarrow )$ 있다.

confluent if and only if for all w, x, and y in A, $x{\stackrel {*}{\leftarrow }}w{\stackrel {*}{\rightarrow }}y$ implies $x{\mathbin {\downarrow }}y$ . Roughly speaking, confluence says that no matter how two paths diverge from a common ancestor (w), the paths공통적인 후계자가 될 겁니다이 개념은 특정 물체 w의 속성으로 정제될 수 있으며, 그 원소가 모두 합체된 경우 합체라고 하는 시스템이다.
A의 모든 w, x, y에Semi-confluent 만일,)← w→ ∗는 y{w\displaystyle x\leftarrow{\stackrel{*}{\rightarrow}}는 y}을 뜻한다)↓ y{\displaystyle x{\mathbin{\downarrow}}는 y}.이 합류 지점에서 w에서 x.에 단일 단계 축소에 따라 차이
국소 만일 A에서 모든 w, x, y,)← w → y{\displaystyle x\leftarrow w\rightarrow y}을 뜻한다)↓ y{\displaystyle x{\mathbin{\downarrow}}는 y}합류.이 속성은 때로는 약하합류라고 불린다.

예locally-confluent에서 rewrite시스템은 Church-Rosser 재산 받지 못하다.

정리.한 ARS을 위하여 다음 세가지 조건:(나는)그것은 Church-Rosser 속성이 있(iii)그것semi-confluent은,(ii), 합류하는 것 같다.[8]

Corollary.[9]회류 ARS에서 if)}그때∗는 y{\displaystyle x{{\stackrel*}{\leftrightarrow}}는 y↔.

만약 둘 다), 어두워져서 정상적인 양식한 다음 = y.
만약 y으로 일반적인 형태, 다음 →∗는 y{\displaystyle x{{\stackrel*}{\rightarrow}}는 y}.

이 equivalences 때문에 변화의 정의에 상당한 문헌이 갖는 것이 있다.예를 들어, Terese의 Church-Rosser 재산과 합류 여기에 익명의 머물러 있지만 해당하는 속성이라 정의된 집합이 정의를 여기서 제공한 와 동일한;Church-Rosser 동의어이곤은 다른 것으로부터 이 출발은 의도적이다 정의되어 있다.[10]위의 당연한 한 더 이상 줄일 수 없는은 y으로 x ↔∗는 y{\displaystyle x{{\stackrel*}{\leftrightarrow}}는 y}속성과 함께 x으로 일반적인 형태는 y을 규정할 수 있다.이 정의, 도서와 오토에서 발견되어, 일반적인 사람 여기 회류 시스템에 주어지지만,이 더non-confluent ARS에 포함됩니다.

반면에 국부혼합은 이 절에 제시된 다른 결합 개념과 동등하지는 않지만, 결합보다 엄격히 약하다.일반적인 counterexample은 국소적으로 혼합되지만 혼합되지 않는( $cf$ . 그림)인 $\{b\rightarrow c,c\rightarrow b,b\rightarrow a,c\rightarrow d\}$ → $\{b\rightarrow c,c\rightarrow b,b\rightarrow a,c\rightarrow d\}$ → $\{b\rightarrow c,c\rightarrow b,b\rightarrow a,c\rightarrow d\}$ → $\{b\rightarrow c,c\rightarrow b,b\rightarrow a,c\rightarrow d\}$ → $\{b\rightarrow c,c\rightarrow b,b\rightarrow a,c\rightarrow d\}$ → $\{b\rightarrow c,c\rightarrow b,b\rightarrow a,c\rightarrow d\}$ → $\{b\rightarrow c,c\rightarrow b,b\rightarrow a,c\rightarrow d\}$ ${\displaystyle \{b\rightarrow c, c\rightarrow b,b\rightarrow a$ 이다.

종료 및 수렴

추상적 재작성 체계는 무한 $x_{0}\rightarrow x_{1}\rightarrow x_{2}\rightarrow \cdots$ x $x_{0}\rightarrow x_{1}\rightarrow x_{2}\rightarrow \cdots$ → $x_{0}\rightarrow x_{1}\rightarrow x_{2}\rightarrow \cdots$ → $x_{0}\rightarrow x_{1}\rightarrow x_{2}\rightarrow \cdots$ 2 → $【\디스플레이스타일 x_{0}\{0$ }\ $오른쪽$ 화살표 x_ ${1}\{1$ }\ $오른쪽$ 화살표 $x_{2}\$ 오른쪽 $화살표$ \cdots $}}}}$ 이(가) 없으면 종료되거나 노에테트리안 관계라고 한다.종단 ARS에서는 모든 물체가 적어도 하나의 정상적인 형태를 가지므로 정상화하고 있다.그 반대는 사실이 아니다.예를 들어, 1의 예로는 시스템이 정상화되고 있음에도 불구하고 $a\rightarrow b\rightarrow a\rightarrow b\rightarrow \cdots$ 리라이딩 체인, $a\rightarrow b\rightarrow a\rightarrow b\rightarrow \cdots$ 즉 $a\rightarrow b\rightarrow a\rightarrow b\rightarrow \cdots$ → $a\rightarrow b\rightarrow a\rightarrow b\rightarrow \cdots$ → a → b → b → b $a\rightarrow b\rightarrow a\rightarrow b\rightarrow \cdots$ → $a\rightarrow b\rightarrow a\rightarrow b\rightarrow \cdots$ → $⋯[\displaystyle a\rightarrow b\rightarrow a\rightarrow$ b\rightarrow $\cdots }$ 이 있다 $a\rightarrow b\rightarrow a\rightarrow b\rightarrow \cdots$ 혼합형 및 종단형 ARS를 표준형,^[11] 또는 수렴형이라고 한다.수렴성 ARS에서는 모든 물체가 독특한 정상 형태를 가지고 있다.그러나 사례 1에서 보듯이 모든 원소에 대해 존재하는 고유한 정규에 대해 시스템이 합체되고 정상화하는 것으로 충분하다.

정리(뉴먼의 보조정리):종료 ARS는 국소적으로 결합되는 경우에만 결합된다.

1942년 뉴먼이 이 결과를 증명하는 원본은 다소 복잡했다.1980년이 되어서야 Huet은 $\rightarrow$ → $\rightarrow$ 이(가) 종료될 $\rightarrow$ 때 근거가 충분한 유도를 적용할 수 있다는 사실을 이용하여 훨씬 간단한 증거를 발표했다.^[12]

참고 항목

단어 문제(수학) - 특히 추상 재작성 시스템에 대한 섹션

메모들

^ 책과 오토, 페이지 9
^ ^a ^b 테레즈, 7페이지
^ ^a ^b 책과 오토, 페이지 10
^ 테레세, 7-8페이지
^ 바더와 닙코우, 8-9페이지
^ 알론조 교회와 J. 바클리 로서.변환의 일부 속성.트랜스. AMS, 39:472-482, 1936
^ 바더와 닙코우, 페이지 9
^ 바더와 닙코우, 페이지 11
^ 바더와 닙코우, 페이지 12
^ 테레세 페이지 11
^ David A. Duffy (1991). Principles of Automated Theorem Proving. Wiley. 여기: 제7.2.1장, 페이지 153
^ 해리슨, 260 페이지

추가 읽기

Baader, Franz; Nipkow, Tobias (1998). Term Rewriting and All That. Cambridge University Press. ISBN 9780521779203. 학부생에게 적합한 교과서.
Nachum Dershowitz and Jean-Pierre Jouannaud Rewrite Systems, Chapter 6 in Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics., Elsevier and MIT Press, 1990, ISBN 0-444-88074-7, pp. 243–320.이 장의 사전 인쇄물은 저자들로부터 자유롭게 구할 수 있지만, 그것은 수치를 놓치고 있다.
로널드 5세 Book and Friedrich Otto, String-rewriting Systems, Springer(1993), ISBN 0-387-97965-4.제1장 "추상적 감축 시스템"
Marc Bezem, Jan Willem Clop, Roel de Vrijer("테레즈"), 용어 재작성 시스템, Cambridge University Press, 2003, ISBN 0-521-39115-6, 1장.이것은 종합적인 단전이다.그러나 다른 곳에서는 흔히 접할 수 없는 공정한 공지와 정의를 사용한다.예를 들어 Church-Roser 속성은 결합과 동일한 것으로 정의된다.
존 해리슨, 캠브리지 대학 출판부, 2009년 ISBN 978-0-521-89957-4, 제4장 "평등"등가 논리의 문제를 해결하는 실용적 관점에서 추상적인 재작성.
Gérard Huet, 혼합물 감소: ACM(JACM) 저널, 1980년 10월, 제27권, 제4권, 페이지 797–821.Huet의 논문은 많은 현대적인 개념, 결과, 그리고 명언을 확립했다.
J. Sinyor; "현악 재작성 시스템으로서의 3x+1 문제", 국제수학수학저널, 2010권(2010), 기사 ID 458563, 6쪽.

[1] 책과 오토, 페이지 9

[terese7-2] 테레즈, 7페이지

[Book_and_Otto,_p._10-3] 책과 오토, 페이지 10

[4] 테레세, 7-8페이지

[5] 바더와 닙코우, 8-9페이지

[6] 알론조 교회와 J. 바클리 로서.변환의 일부 속성.트랜스. AMS, 39:472-482, 1936

[7] 바더와 닙코우, 페이지 9

[8] 바더와 닙코우, 페이지 11

[9] 바더와 닙코우, 페이지 12

[10] 테레세 페이지 11

[11] David A. Duffy (1991). Principles of Automated Theorem Proving. Wiley. 여기: 제7.2.1장, 페이지 153

[12] 해리슨, 260 페이지

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[11]

[12]

Search