트레이스 모노이드

컴퓨터 과학에서 추적은 문자열의 집합으로, 문자열의 특정 문자는 통근할 수 있지만 다른 문자는 통근할 수 없다.문자열이 항상 정해진 순서가 아니라 일정한 개각을 허용함으로써 문자열의 개념을 일반화한다.흔적은 1969년 피에르 카르티에와 도미니크 포아타에 의해 맥마혼의 마스터 정리에 대한 결합 증거를 주기 위해 도입되었다.동시 연산 이론에는 트레이스가 사용되는데, 여기서 통근 문자는 서로 독립적으로 실행할 수 있는 작업의 일부를 의미하며, 비커밍 문자는 잠금, 동기화 포인트 또는 스레드 결합을 의미한다.^[1]

트레이스 모노이드 또는 자유 부분 교환 모노이드 는 트레이스의 모노이드다.간단히 말해서, 그것은 다음과 같이 구성된다: 일련의 통근 편지는 독립적 관계에 의해 주어진다.이는 등가 문자열의 등가 관계를 유도하며, 등가 등급의 요소는 트레이스다.그런 다음 등가 관계는 자유 모노이드(유한 길이의 모든 문자열 집합)를 등가 등급 집합으로 분할한다. 그 결과는 여전히 단일형이며, 지수 모노이드이며 추적 모노이드라고 불린다.모든 종속성 동형(아래 참조) 모노이드들이 사실 이형동형이라는 점에서 추적 모노이드는 보편적이다.

추적 모노이드들은 공정 계산의 기초를 형성하면서 동시 연산을 모형화하는 데 일반적으로 사용된다.그들은 미량 이론의 연구 대상이다.미량 모노이드의 효용은 그것들이 이형성이라는 사실에서 의존성 그래프의 단조로움으로 인해 발생하며, 따라서 대수적 기법을 그래프에 적용할 수 있게 하고, 그 반대의 경우도 마찬가지다.그들은 또한 하나 이상의 컴퓨터에서 예정된 모든 프로세스의 맥락에서 개별 프로세스의 계산의 역사를 모델링하는 역사 모노이드와 이형적이다.

트레이스

${\$은(는) 자유 모노이드, 즉 알파벳 $\sigma {\displaystyle \mathrm{}}$ ${\displaystyle \Sigma }}}$에 쓰여진 모든 문자열 집합을 가리킨다$$$.$여기 별표는 평소와 같이 클레인 별을 가리킨다.An independency relation ${\displaystyle I}$ on ${\displaystyle \Sigma }$ then induces a binary relation ${\displaystyle \sim }$ on ${\displaystyle \Sigma ^{*}}$, where ${\displaystyle u\sim v}$ if and only if there exist ${\displaystyle x,y\in \Sigma ^{*}}$, and a pair ${\displaystyle (}$${\displaystyle (a,b)\in I}$ such that ${\displaystyle u=xaby}$ and ${\displaystyle v=xbay}$. Here, ${\displaystyle u,v,x}$ and ${\displaystyle y}$ are understood to be strings (elements of ${\displaystyle \Sigma ^{*}}$), while ${\displaystyle a}$ and $$${\displaystyle b}$ ${\displaystyle b}$은(는) 문자($EX{\displaystyle \mathrm{}}$ ${\displaystyle \Sigma }$의 요소).$$

트레이스는${\displaystyle }$~ ${\displaystyle \sim}$의 대칭, 반사, 전이적 폐쇄로 정의된다$.$ 따라서 트레이스는 $on{\displaystyle {\mathrm{}}^{}}$ {${\$에$$동등성 관계로서 $\equiv {\displaystyle {}_{}}$ ${\displaystyle D_{}}$ ${\$로 표시된다$.$ 동등성에 대한 첨자 D는 단순히 동등성을 얻음을 나타낸다.종속성 D에 의해 유도된 독립성.분명히 다른 의존성은 다른 동등성 관계를 줄 것이다.

The transitive closure simply implies that ${\displaystyle u\equiv v}$ if and only if there exists a sequence of strings ${\displaystyle (w_{0},w_{1},\cdots ,w_{n})}$ such that ${\displaystyle u\sim w_{0}}$ and ${\displaystyle v\sim w_{n}}$ and ${\displaystyle w_i\sim {}_{}}$${\displaystyle {\mathrm{w}}_{}}$ ${\displaystyle i_{}}$+ 1$${\$displaystyle w_{i}\sim w_{i+1},$ < n ${\displaystyle 0\leq$ i$<n}$.${\$concatenation)에 대한 모노이드 조작에 따라 트레이스가 안정적이며, $따라서{\displaystyle {\mathrm{}}^{}}$ ∗ ${\$에 대한 일치 관계가 된다$.$

일반적으로 $M{\displaystyle \mathbb{}(D}$) ${\displaystyle \mathb {M}(D$으)로 표시되는 트레이스 모노이드 는 지수 모노이드로 정의된다.

${\displaystyle \mathb {M}(D)=\Sigma ^{*}/\equiv _{D}}}$

동형성

${\displaystyle \phi _{D}\Sigma ^{*}\to \mathb {M}(D)}$

일반적으로 자연 동형성 또는 표준 동형성이라고 한다.자연적 또는 표준적이라는 용어가 마땅하다는 것은 이 형태론이 후장에서 논의한 바와 같이 보편적 속성을 구체화한다는 사실에서 비롯된다.

예

알파벳 $\sigma {\displaystyle \mathrm{}}$=${\displaystyle }${ ${\displaystyle a,}$ ${\displaystyle b,}$ ${\displaystyle c}$ ${\displaystyle \}}$ ${\displaystyle \Sigma =\{a,b,c\}}$을(를) 고려하십시오$.$ 가능한 종속관계는 다음과 같다.

${\displaystyle {\begin{matrix}D&=&\{a,b\}\times \{a,b\}\quad \cup \quad \{a,c\}\times \{a,c\}\\&=&\{a,b\}^{2}\cup \{a,c\}^{2}\\&=&\{(a,b),(b,a),(a,c),(c,a),(a,a),(b,b),(c,c)\}\end{matrix}}}$

그에 상응하는 독립성은

${\displaystyle I_{D}=\{(b,c)\\,(c,b)\}}$

따라서 글자 $b{\displaystyle ,}$ ${\displaystyle c}$ ${\displaystyle b,c}$ 통근한다$$.따라서$$ 예를 들어, $a{\displaystyle }$ b ${\displaystyle a}$ b ${\displaystyle a}$ b ${\displaystyle c}$ ${\displaystyle abababbca}$ 문자열의 추적 동등성 클래스는

$(\displaystyle [abababbbca])_{D}=\{ababbbca\...\;abbabcba\\;ababba\}}$

${\displaystyle {동등성}_{}}$ 등급${\displaystyle }$[${\displaystyle a}$ b ${\displaystyle a}$ ${\displaystyle b}$ a b ${\displaystyle a}$ b ${\displaystyle c}$ ${\displaystyle a}$ ${\displaystyle {}_{}}$ D ${\$${{D}}$은 트레이스 모노이드의 원소다.

특성.

취소특성은 균등성이 권리취소에서도 유지된다고 명시하고 있다.That is, if ${\displaystyle w\equiv v}$, then ${\displaystyle (w\div a)\equiv (v\div a)}$. Here, the notation ${\displaystyle w\div a}$ denotes right cancellation, the removal of the first occurrence of the letter a from the string w, starting from the right-hand side.좌취소에도 동등성이 유지된다.다음과 같은 여러 가지 요점이 있다.

• 임베딩: x와 y 문자열의 경우$$ w ${\displaystyle w}$${\displaystyle v}$ ${\displaystyle w\equiv v}($$x$ w w w ${\displaystyle \equiv }$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle xwy\equiv xvy}$만 해당)따라서, 미량 모노이드는 통사적 모노이드다.
• 독립성: ${\displaystyle uv}$ ${\displaystyle ua\equiv vb}$과(와)${\displaystyle u}$ b ${\displaystyle a\neq b}$인 경우 a는 b와 독립적이다$.$${\displaystyle 즉},{\displaystyle }$ ${\displaystyle (,}$ ${\displaystyle b}$) ${\displaystyle \in }$ ${\displaystyle {}_{}}$ ${\displaystyle D_{}}$ ${\$ 게다가 $u{\displaystyle w}$ w ${\displaystyle$ $u$$\equiv wb},$ $v$ ${\displaystyle \equiv }$ ${\displaystyle w}$ ${\displaystyle$v\$equiv wa}$과 같은 문자열도 존재한다$.$
• 투영 규칙: 동등성은 문자열 투영에서 유지되므로 $w{\displaystyle }$ ${\displaystyle \equiv }$ ${\displaystyle v}$ ${\displaystyle w\equiv v$ ${\displaystyle {if\mathrm{}}_{}}$ ${\displaystyle (}$π ( w ) ${\displaystyle {}_{}{\pi \mathrm{}}_{}}$ (${\displaystyle v}$ ${\displaystyle )}$ ${\displaystyle \pi$ _${\Sigma$}($w)\equiv \pi$ _${\Sigma$}($v)$.

리바이스 보조정리기의 강한 형태는 흔적을 간직하고 있다.Specifically, if ${\displaystyle uv\equiv xy}$ for strings u, v, x, y, then there exist strings ${\displaystyle z_{1},z_{2},z_{3}}$ and ${\displaystyle z_{4}}$ such that ${\displaystyle (w_{2},w_{3})\in I_{D}}$ for all letters ${\$$displaystyle w_{$2}\$in$ \Sigma $}$ 및 w$$ ${\displaystyle {3\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \mathrm{\sigma }}$ $\$ {\$displaystyle w_{2}}:$$z$ 2 ${\$ $w{\displaystyle {}_{}}$ {\displaystystyle $w_{$3}}이 $z{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ ${\$에 발생하도록$}$

${\displaystyle u\equiv z_{1}z_{2},\qquad v\equiv z_{3}z_{4},}$

${\displaystyle x\equiv z_{1}z_{3},\qquad y\equiv z_{2}z_{4}.}$^[2]

보편적 재산

종속성 형태론(상속성 D에 관한)은 형태론이다.

${\displaystyle \psi :\Sigma ^{*}\to M}$

일부 모노이드 M에 "상용" 추적 속성이 유지되도록, 즉 다음과 같이 한다.

1. ${\displaystyle \psi }$( w${\displaystyle }$)${\displaystyle }$= ${\displaystyle \psi }$ (${\displaystyle \epsilon }$ ) ${\displaystyle \psi (w)=\displaystyle$ w$=\varepsilon )}$은 $w{\displaystyle }$= ${\displaystyle \epsilon }$ ${\displaystyle w=\varepsilon }$을 암시한다$$.

2.${\displaystyle }$( ${\displaystyle a}$, b${\displaystyle }$) ${\displaystyle \in }$ ${\displaystyle I_{}}$ ${\displaystyle {}_{}}$ ${\$는 $\psi {\displaystyle }$(${\displaystyle b}$ ${\displaystyle )}$ =${\displaystyle \psi }$ ${\displaystyle (b)}$ ${\displaystyle \psi (ab)=\psi (ba)}$을 암시한다$$.

3. $\psi {\displaystyle }$ (${\displaystyle u}$ a )${\displaystyle }$= ${\displaystyle \psi }$ ${\displaystyle (v}$) ${\displaystyle \psi (ua)=\psi (v)}$는 $\psi {\displaystyle }$(${\displaystyle u}$)${\displaystyle }$= ${\displaystyle \psi }$ ${\displaystyle (v}$)${\displaystyle \psi (u)=\div a)}$을 의미한다$$.

4. $\psi {\displaystyle }$ (${\displaystyle u}$ a )${\displaystyle }$= ${\displaystyle \psi }$ ${\displaystyle (v}$ ${\displaystyle b}$) ${\displaystyle \psi (ua)=\psi (vb)}$ 및 ${\displaystyle \ne }$ ${\displaystyle b}$ ${\displaystyle a\neq b}$은(,${\displaystyle b}$) ${\displaystyle \in }$ ${\displaystyle I_{}}$ D ${\$을 의미함

Dependency morphisms are universal, in the sense that for a given, fixed dependency D, if ${\displaystyle \psi :\Sigma ^{*}\to M}$ is a dependency morphism to a monoid M, then M is isomorphic to the trace monoid ${\displaystyle \mathbb {M} (D)}$. In particular, the natural homomorphism is a dependency morphism.

정상형식

이 구간은 확장이 필요하다.덧셈으로 도와줘도 된다.(2009년 12월)

미량 모노이드에 있는 단어에는 두 가지 잘 알려진 정상적인 형태가 있다.하나는 아나톨리 5세에 의한 사전적 정상형식이다.아니시모프와 도널드 크누스, 그리고 다른 하나는 1960년대에 콤비네이터를 위해 추적 모노이드를 연구한 피에르 카르티에와 도미니크 포아타 때문에 포아타 정상형이다.

추적 언어

$정식{\displaystyle {\mathrm{}}^{}}$ 언어가 $∗{\$ 가능한 모든 문자열 집합의$$ 하위 집합으로 간주될 수 있듯이, 따라서 추적 언어는 M ( $D{\displaystyle \mathbb{}}$ ) ${\displaystyle$ 가능한 모든$$ 트레이스의 하위 집합으로 정의된다.

${\displaystyle {\mathrm{}}^{}}$ $L{\displaystyle }$ ${\displaystyle \subseteq }$ ∗ ${\displaystyle {\{}^{}}$ $\$ {\$displaystyle$L\$subseteq \Sigma$^{*}}}}은 추적 언어이거나$$, 만일 그렇다면 종속성 D와 일치한다고 한다.

${\displaystyle L=[L]_{D}}$

어디에

${\displaystyle [L]_{D}=\빅컵 _{w\in L}[w]_{D}$

끈 집합의 추적 폐쇄야

참고 항목

• 추적 캐시

메모들

참조

일반참조

• Diekert, Volker; Métivier, Yves (1997), "Partial Commutation and Traces", in Rozenberg, G.; Salomaa, A. (eds.), Handbook of Formal Languages Vol. 3; Beyond Words, Springer-Verlag, Berlin, pp. 457–534, ISBN 3-540-60649-1
• Lothaire, M. (2011), Algebraic combinatorics on words, Encyclopedia of Mathematics and Its Applications, vol. 90, With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.), Cambridge University Press, ISBN 978-0-521-18071-9, Zbl 1221.68183
• 안토니 마주르키에비치, 「추적 이론의 도입」 페이지 3-41, <추적서 V>.디케르트, G. 로젠버그, eds. (1995) 월드 사이언티픽, 싱가포르 ISBN 981-02-2058-8
• 볼커 다이커트, 추적에 대한 콤비네이터틱스, LNCS 454, 스프링거, 1990, ISBN 3-540-53031-2, 페이지 9–29
• Sándor, Jozsef; Crstici, Borislav (2004), Handbook of number theory II, Dordrecht: Kluwer Academic, pp. 32–36, ISBN 1-4020-2546-7, Zbl 1079.11001

세미날 출판물

• Pierre Cartier and Dominique Foata, Problems 콤비나토레스 de communation et raarrarranges, 수학 85, Springer-Verlag, 1969, 2006 Free를 새로운 부록으로 재인쇄하다
• Antoni Mazurkiewicz, Concurrent 프로그램 구성 및 해석, DIMI Report PB 78, Arhus University, 1977