히스토리 모노이드

수학과 컴퓨터 과학에서, 역사 모노이드란 컴퓨터 프로세스를 동시에 실행하는 역사를 문자열의 집합으로 표현하는 방법인데, 각 문자열은 과정의 개별적인 역사를 나타낸다.History monoid는 독립적으로 실행되는 프로세스 또는 스레드 집합 사이에 랑데부 지점을 제공하기 위한 동기화 원시 요소 집합(잠금, 뮤텍스 또는 스레드 결합 등)을 제공한다.

역사 모노이드들은 동시 연산 이론에서 발생하며, 순차적 과정을 전달하는 언어 CSP나 통신 시스템의 미적분인 CCS와 같이 공정 계산에 대한 낮은 수준의 수학 기반을 제공한다.역사 모노이드들은 처음에 M.W. 쉴즈에 의해 제시되었다.^[1]

역사 모노이드들은 모노이드(자유롭게 부분적으로 교환되는 모노이드)를 추적하고 의존성 그래프의 모노이드에 대해 이형성이다.이와 같이, 그것들은 자유로운 물건이며 보편적이다.히스토리 모노이드(history monoid)는 모노이드의 범주에 속하는 반아벨라 범주형 제품의 일종이다.

제품 모노이드 및 투영

내버려두다

${\displaystyle A=(\Sigma _{1},\Sigma _{2},\ldots,\Sigma _{n}})$

(반복적으로 분할할 필요는 없음) 알파벳 ${\displaystyle n_{}}$ k {\$displaystyle \Sigma _{k}$의 n-tuple을 ${\displaystyle \mathrm{나타낸다}}$$.$ Let $P{\displaystyle (}$A ){\$displaystyle P(A)}$는 각 알파벳에서 하나의 유한 길이 문자열의 가능한 모든 조합을 나타낸다$$.

${\displaystyle P(A)=\Sigma _{1}^{*}\time \Sigma _{2}^{*}\time \cdots \time \time \Sigma _{n}^}}}}}}}}}$

(좀 더 격식 있는 언어로 표현하면${\displaystyle ,}$ $P{\displaystyle }$ ($){\displaystyle P(A)}$는 ${\displaystyle {\sigma }_{}}$k {\$displaystyle \Sigma _{$k}}}의 자유 모노이드의 데카르트 제품이다$.$위첨자 별은 클레인 별이다.)제품 모노이드의 구성은 구성 요소별로 구성되므로

${\displaystyle \mathbf {u} =(u_{1},u_{2},\ldots,u_{n},},}$

그리고

${\displaystyle \mathbf {v} =(v_{1},v_{2},\ldots,v_{n},},}$

그때

${\displaystyle \mathbf {uv} =(u_{1}v_{1},u_{2}v_{2},\ldots,u_{n}v_{n}}}\,},}$

$모든{\displaystyle }$${\displaystyle }u{\displaystyle \mathbf{}}$ , ${\displaystyle v\mathbf{}}$ ${\$,\$mathbf {v}$ in P$A$ $조합$ 알파벳을$$ 정의하십시오.

$\displaystyle \Sigma =\Sigma _{1}\cup \Sigma _{2}\cdots \cdots \cup \Sigma _{n}\,}$

(여기 있는 조합은 정해진 조합이지 해체된 조합이 아니다.)${\displaystyle \in }$ ∈ \$$ {\$displaystyle w\in \Sigma$ $^\{*\}\}\}\}\}\}\}\{\backslash$$displaystyle$의 문자만 해당$$ 문자열 투영법 ${\displaystyle {\pi }_{}}$k : ${\displaystyle {\mathrm{}}_{}^{}{}^{}}$\$$\{\$displaystyleption \pi$ \pi $_{k:$$\Sigma ^{*}\to \Sigma _{k}^{*}}$. A distribution ${\displaystyle \pi :\Sigma ^{*}\to P(A)}$ is the mapping that operates on ${\displaystyle w\in \Sigma ^{*}}$ with all of the ${\displaystyle \pi _{k}}$, separating it into components in each free monoid:

${\displaystyle \pi (w)\mapsto(\pi _{1}(w),\pi _{2}(w),\ldots ,\pi _{n}(w)\,},}$

역사

${\displaystyle \in }$ { ${\displaystyle a\in \Sigma }$에 대해 tuple $\pi {\displaystyle }$(${\displaystyle }$) ${\displaystyle \pi (a)}$을(를) a의 기본 역사라고 한다$$$.$$알파벳{\displaystyle {\mathrm{}}_{}}$ ${\$에 a자를 포함시키는 지표 함수 역할을 한다$.$ 즉,

${\displaystyle \pi (a)=(a_{1},a_{2},\ldots,a_{n}}}$

어디에

${\displaystyle a_{k}={\begin{case}a{{\mbox{{}a\in \Sigma _{k}\\barepsilon{\mbox{nother}}}}.\end{case}}}$

여기서 $\epsilon {\displaystyle }$ ${\displaystyle \varepsilon }$은 빈 문자열을 가리킨다.The history monoid ${\displaystyle H(A)}$ is the submonoid of the product monoid ${\displaystyle P(A)}$ generated by the elementary histories: ${\displaystyle H(A)=\{\pi (a) a\in \Sigma \}^{*}}$ (where the superscript star is the Kleene star applied with a component-wise defi위와 같이 작문한다.H${\displaystyle }$( ${\displaystyle A}$) ${\displaystyle H(A)}$의 요소를 글로벌 역사라고 하며$$, 글로벌 역사의 투영도 개별 역사라고 한다.

컴퓨터 과학과의 연결

이 맥락에서 단어 히스토리의 사용과 동시 컴퓨팅과의 연결은 다음과 같이 이해할 수 있다.개별 이력은 프로세스(또는 나사산 또는 기계)의 상태 순서에 대한 기록이며 알파벳 ${\displaystyle {alphabet}_{}}$ k ${\$는 프로세스의$$ 상태 집합이다.

둘 이상의 알파벳에서 발생하는 문자는 다양한 개별 이력 사이의 동기화 원시적인 역할을 한다.즉, 그러한 편지가 한 개인의 역사에서 일어난다면 그것은 또 다른 역사에서도 일어나야 하며, 그들을 함께 '타이'하거나 '렌즈'하는 역할을 한다.

예를 들어 $\sigma {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$=${\displaystyle }${ ${\displaystyle a,}$ ${\displaystyle b,}$ ${\displaystyle c}$ ${\displaystyle \}}$ ${\displaystyle \Sigma _{1}=\{a,b,c\}}$ 및$$ $\sigma {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$=${\displaystyle }${ ${\displaystyle a,}$ ${\displaystyle d,}$ ${\displaystyle e\}}$ ${\displaystyle \Sigma _{2}=\a,d,e\}}}}$을 고려하십시오$.$조합 알파벳은 물론 $\sigma {\displaystyle \mathrm{}}$=${\displaystyle }${ ${\displaystyle a,}$ ${\displaystyle b,}$ ${\displaystyle c,}$ ${\displaystyle d,}$ ${\displaystyle e}$} ${\displaystyle \Sigma =\{a,b,c,d,e\}}$이다$.$The elementary histories are ${\displaystyle (a,a)}$, ${\displaystyle (b,\varepsilon )}$, ${\displaystyle (c,\varepsilon )}$, ${\displaystyle (\varepsilon ,d)}$ and ${\displaystyle (\varepsilon ,e)}$. In this example, an individual history of the first process might be $b{\displaystyle }$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle c}$ ${\displaystyle bcbcc}$ 반면$$ 두 번째 시스템의 개별 히스토리는 $d{\displaystyle }$ ${\displaystyle d}$ d ${\displaystyle d}$ ${\displaystyle d}$ d ${\$$displaystyle$ $dddddd$$}$일 수 있다$.$ 이 문자열을 개별 알파벳에 투영하면 i가 되기 때문에 이 두 개별 히스토리는 모두 글로벌 $히스토리{\displaystyle }$ ${\displaystyle b}$ ${\displaystyle d}$ d d ${\displaystyle d}$ d d d d c ${\displaystyle d}$ c d c d d d ${\displaystyle d}$ d e d d d d d d d d d d d d d d d d d d ${\displaystyle \mathrm{ddd}}$ $dd$ d d dd d d d$$d d d d d d d d dd dd dd dd d d d d무분할의 역사글로벌 역사에서 $b{\displaystyle }$ ${\displaystyle$ b$}$과 c ${\displaystyle c}$은 개별 이력을 변경하지 않고 재배열할 수 있다는 점에서 $d{\displaystyle }$ ${\displaystyle d}$과 $e{\displaystyle }$ ${\displaystyle$ e$\}$과 함께 통근하는 것으로 간주할$$ 수 있다.이러한 감화는 단순히 첫 번째 프로세스와 두 번째 프로세스가 동시에 실행되고 있으며 서로에 대해 정렬되지 않은 상태라는 것을 나타내는 것이다; 그들은 어떤 메시지를 교환하거나 동기화를 수행하지 않았다.

$문자{\displaystyle }$a {\$displaystyle$ a$}$은(는) 동기화 원시 역할을$$ 하는데, 그 발생은 글로벌 역사 및 개별 역사 모두에 있는 한 지점을 나타내며, 이 두 글자는 서로 나눌 수 없다.따라서 문자 $b{\displaystyle }$ ${\displaystyle b}$ $및$ c ${\displaystyle c}$을(를) $d{\displaystyle }$ ${\displaystyle d}$ 및 $e$ ${\displaystyle e}$을(를) 지나 다시 정렬할 수 없지만$$ ${\displaystyle a}$을(를) 지나 다시 정렬할 수는 없다$.$따라서 $글로벌{\displaystyle }$ 역사 ${\displaystyle b}$ $d{\displaystyle }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle e}$ ${\displaystyle bdatabe}$ 및 글로벌$$ 역사 b ${\displaystyle d}$ a ${\displaystyle e}$ ${\displaystyle b}$ ${\$$displaystyle$ $bdcaeb}$은 모두 ${\displaystyle \mathrm{개별}}$ 이력 $b{\displaystyle }$ ${\displaystyle c}$ ${\$displaystyle $bcab$$}$ 및$$$$${\displaystyle d}$ ${\displaystyle e}${\$displaystyd}$의 실행 $전후$에$$발생할 수 $있음$을 나타낸다.$스타일{\displaystyle }$ $c$ 그러나 e$$${\$$displaystyle$ a}은$($는) 동기화되므로$$ e {\$displaystyle e}$이($)$ c {\displaystyle c$\}$과(와) 다른 프로세스에 있더라도 c {\$displaystystyle$ $c}$ 뒤에 $e{\displaystyle }$ ${\displaystystystyle$ c$}$이(가$)$가 발생하도록 보장된다$.$

특성.

히스토리 모노이드(history monoid)는 미량 모노이드에 대해 이형성이며, 이와 같이 모노이드의 범주에 속하는 반아벨주의 범주형 제품의 일종이다.In particular, the history monoid ${\displaystyle H(\Sigma _{1},\Sigma _{2},\ldots ,\Sigma _{n})}$ is isomorphic to the trace monoid ${\displaystyle \mathbb {M} (D)}$ with the dependency relation given by

$\displaystyle D=\lift(\Sigma _{1}\time \Sigma _{1}\right)\ \left(\Sigma _{2}\time \Sigma \{n}\rigma \n}\rigma \rigma \rigma.}$

간단히 말해서, 이것은 위에서 주어진 비공식 논의의 공식적인 설명일 뿐이다: 알파벳 ${\displaystyle {alphabet}_{}}$ k ${\$의 문자는 두 알파벳에서 모두 발생하는 문자가 아닌 한 $alphabet{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle j_{}}$ ${\$ 알파벳 \j}에 있는 문자들을 기준으로 정렬할 수 있다$$$.$따라서, 흔적은 정확히 세계적인 역사고, 그 반대도 마찬가지다.

Conversely, given any trace monoid ${\displaystyle \mathbb {M} (D)}$, one can construct an isomorphic history monoid by taking a sequence of alphabets ${\displaystyle \Sigma _{a,b}=\{a,b\}}$ where ${\displaystyle (a,b)}$ ranges over all pairs in ${\displaystyle D}$.

메모들

참조

• 안토니 마주르키에비치, 「추적 이론의 도입」 페이지 3-41, <추적서 V>.디케르트, G. 로젠버그, 에드스(1995) 월드 사이언티픽, 싱가포르 ISBN981-02-2058-8
• 볼커 디케르트, 이브 메티비에르, "부분적 감응과 추적", 인 지 로젠베르크와 A. Salomaa, 편집자, 공식 언어 핸드북, 제3권, 비욘드 워즈, 457-534페이지.1997년 베를린 스프링거-베를라크.