세미그룹 작용

대수학 및 이론 컴퓨터 과학에서, 집합에 있는 세미그룹의 작용이나 행위는 세미그룹의 각 요소와 연관되어 세미그룹의 두 요소(세미그룹 연산 사용)의 곱이 해당 두 가지 변환의 복합성과 연관되도록 세트의 변환을 연관시키는 규칙이다.이 용어는 세미그룹의 요소들이 세트의 변혁으로 작용하고 있다는 생각을 전달한다.대수학적 관점에서, 세미그룹 작용은 그룹 이론에서 그룹 작용의 개념을 일반화한 것이다.컴퓨터 과학의 관점에서, 세미그룹 활동은 자동화와 밀접하게 관련되어 있다: 집합모델은 자동화의 상태와 입력에 대응한 그 상태의 행동모델 변환이다.

중요한 특수한 경우는 세미그룹이 모노이드인 동시에 모노이드의 아이덴티티 요소가 집합의 아이덴티티 변환으로 작용하는 모노이드 작용이나 행위다.범주의 이론적 관점에서, 모노이드란 하나의 개체를 가진 범주로, 행위란 그 범주에서 집합의 범주로 이어지는 방편이다.이것은 즉시 집합의 범주가 아닌 범주의 객체에 대한 모노이드 작용에 일반화를 제공한다.

또 다른 중요한 특별한 경우는 변환 세미그룹이다.이것은 집합의 변환의 세미그룹이며, 따라서 집합에 대한 자동적 작용을 가지고 있다.이 개념은 케일리의 정리의 아날로그에 의해 세미그룹의 보다 일반적인 개념과 연결된다.

(용어에 대한 참고사항: 이 영역에서 사용되는 용어는 저자에 따라 때때로 상당히 다르다.자세한 내용은 기사를 참조하십시오.)

형식 정의

S를 세미그룹으로 하자.그 후 S의 (좌)세미그룹 작용(또는 행위)은 수술과 함께 설정된 X로 다음과 같이 세미그룹 동작 operation과 호환되는 • : S × X → X이다.

• 모든 s에 대해, t in S와 x in X, s • (t • x) = (s ∗ t) • x.

이것은 a(왼쪽) 그룹 작용의 세미그룹 이론에서 아날로그적인 것으로, X의 함수 집합에 있는 세미그룹 동형성에 해당한다.오른쪽 세미그룹 동작은 조작 • X × S → X 만족 (x • a) • b = x • (a ∗ b)를 이용하여 유사한 방식으로 정의된다.

M이 단조인 경우, M의 (왼쪽) 단조 작용(또는 행위)은 M의 (왼쪽) 세미그룹 작용이며, 추가 속성은 다음과 같다.

• X의 모든 X에 대해: e • x = x

여기서 e는 M의 아이덴티티 요소다.이것은 그에 상응하여 단성 동형성을 부여한다.오른쪽 모노이드 작용은 유사한 방법으로 정의된다.세트에 작용이 있는 모노이드 M을 연산자 모노이드라고도 한다.

S on X에 대한 S의 세미그룹 작용은 Sem그룹에 정체성을 결합하고 그것이 X에 대한 정체성 변환의 역할을 하도록 요구함으로써 모노이드 작용으로 만들어질 수 있다.

용어와 표기법

S가 세미그룹이나 모노이드인 경우, S가 위와 같이 작용하는 세트 X(왼쪽, 말하자면 왼쪽)를 S-act, S-set, S-action, S-operand 또는 S-operand 또는 S-over S.일부 저자는 ID 요소가 없을 때 ID 공리(e • x = x)를 비어 있는 것으로 간주하거나, ID가 있는 S-act에 대해 단일 S-act라는 용어를 사용함으로써 세미그룹과 모노이드 액션을 구분하지 않는다.^[1]

행위의 정의 속성은 세미그룹 운영의 연관성과 유사하며, 모든 괄호를 생략할 수 있다는 것을 의미한다.특히 컴퓨터 공학에서는 세미그룹 운영과 그 작용이 병행하여 나타나도록 운영도 생략하는 것이 일반적인 관행이다.이러한 방식으로 S에서 온 문자열이 s에 대한 stx, S에 대한 t, X에 대한 x의 표현에서와 같이 X에 작용한다.

좌극보다는 우극으로 일하는 것도 꽤 흔한 일이다.^[2]그러나 모든 오른쪽 S-act는 S와 같은 요소를 가지지만 인자를 역행하여 곱셈이 정의되는 반대쪽 세미그룹에 대한 좌행위로 해석할 수 있으므로, s • t = t • s를 역행하여 두 개념은 본질적으로 동등하다.여기서 우리는 주로 좌익행위의 관점을 채택한다.

행위 및 변형

기능을 나타내기 위해 $T{\displaystyle }$ ${\displaystyle T$과 같은 문자를 사용하는 것이 종종 편리하다(예: 고려 중인 행위가 둘 이상인 경우).

$T\colon S\time X\to X}$

$S{\displaystyle }$ ${\displaystyle S}$ -action을$$ 정의하여 s${\displaystyle }s{\displaystyle }$ ${\displaystyle x}$ {\$displaystyle s\cdot x$ 대신$$ $T{\displaystyle (s}$, ${\displaystyle x}$) ${\displaystyle T(s,x)}$를 쓴다.$S{\displaystyle }$ ${\displaystyle S}$의 s ${\displaystyle$ s$}$에 대해 다음을 가리킨다$.$

${\displaystyle T_{s}\colon X\to X}$

$다음$에 의해 정의된$$ X ${\displaystyle X}$의 변환

$[\displaystyle T_{s}(x)=T(s,x)]}$

$S{\displaystyle }$ ${\displaystyle S}$ -act의$$ 정의 속성에 의해 $T{\displaystyle }$ ${\displaystyle T}$이(가) 충족됨

${\displaystyle T_{s*t}=T_{s}\circule T_{t}.}$

또한 함수 $s{\displaystyle }$ ${\displaystyle \mapsto }$ ${\displaystyle T_{}}$ s ${\$을 고려하십시오$.$ ${\displaystyle \mathrm{카레}}$ ${\displaystyle }$ ${\displaystyle (T}$)${\displaystyle }$: ${\displaystyle S}$→${\displaystyle }$( ${\displaystyle X}$→ ${\displaystyle X}$) ${\displaysty \operatorname {curry} (T):$$S\to(X\to$ X$)}($Curring 참조).${\displaystyle \mathrm{카레}}$ ${\displaystyle \operatorname {curry}}$은(는) 바이어싱이기$$ 때문에 세미그룹 작업은 만족하는$$ 함수 $S{\displaystyle }$→${\displaystyle }$(${\displaystyle X}$→ ${\displaystyle X}$) ${\displaysty S\to (X\to X)}$로 정의할 수 있다.

${\displaystyle \operatorname {curry}(T)=\operatorname {curry}(T)\circule \operatorname {curry}(T)(t)}$

That is, ${\displaystyle T}$ is a semigroup action of ${\displaystyle S}$ on ${\displaystyle X}$ if and only if ${\displaystyle \operatorname {curry} (T)}$ is a semigroup homomorphism from ${\displaystyle S}$ to the full transformation monoid of ${\displaystyle X}$.

S-호모형성

X와 X를 S-acts로 하자.그렇다면 X부터 X까지 S-호모형은 지도가 된다.

$F\colon X\to X'}$

그런

${\displaystyle }$${\displaystyle \mathrm{모든}}$ $s{\displaystyle }$${\displaystyle x}$S${\displaystyle }${\$displaystyle s\in S}$ 및$$ $x{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle X}$ ${\displaystyle x\in X}$에 대해 F${\displaystyle (s}$) = ${\displaystyle s}$(${\displaystyle x)}$ ${\displaystyle F(sx)=sF(x$$)\}.$

그러한 모든 S-호모형성의 집합은 $일반적$으로 H ${\displaystyle {\mathrm{o}}_{}}$ m ${\displaystyle {}_{}}$(${\displaystyle {}^{}}$, X ${\displaystyle {\prime }^{}}$) ${\displaystyle \mathrm {Hom} _{S}(X,X')$로 쓰여진다$.$

M-acts의 M-호모형은, M에 대해, 단모형 M에 대해 정확히 같은 방법으로 정의된다.

S-Act와 M-Act

고정된 세미그룹 S의 경우, 왼쪽 S-act는 S-Act로 표시된 범주의 객체로서, S-homorphism은 S-homorphism이다.오른쪽 S-acts의 해당 범주는 Act-S로 표시되기도 한다(링 위에 있는 왼쪽 및 오른쪽 모듈의 범주 R-Mod 및 Mod-R과 유사하다).

모노이드 M의 경우, M-Act와 Act-M 범주는 동일한 방식으로 정의된다.

예

• 모든 sem그룹(${\displaystyle S}$ ,${\displaystyle \ast }$) ${\displaystyle(S,*)$은 $S{\displaystyle }$ ${\displaystyle S}$에 대한 작업을 가지고$$ 있다$.$ 여기서${\displaystyle }$where${\displaystyle }$= ${\displaystyle \ast }$ =$$\$displaystyle \cdot$ $=*\}.$ 작업 속성은 $\ast {\displaystyle }$ ${\displaystyle *}$의 연관성으로 인해 유지된다$.$
• More generally, for any semigroup homomorphism ${\displaystyle F\colon (S,*)\rightarrow (T,\oplus )}$, the semigroup ${\displaystyle (S,*)}$ has an action on ${\displaystyle T}$ given by ${\displaystyle s\cdot t=F(s)\oplus t}$.
• $모든{\displaystyle }$ X ${\displaystyle$ X$}$에 대해 X$$let $displaystyle$X^{*}}을$($를) $X{\displaystyle }$ ${\displaystyle X$ 요소의 시퀀스 집합으로$$ 설정하십시오.The semigroup ${\displaystyle (\mathbb {N} ,\times )}$ has an action on ${\displaystyle X^{*}}$ given by ${\displaystyle n\cdot s=s^{n}}$ (where ${\displaystyle s^{n}}$ denotes ${\displaystyle s}$ repeated ${\displaystyle n}$ times).
• 세미그룹$({\displaystyle N\mathbb{}}$, ${\displaystyle \times }$) ${\displaystyle(\mathb {N} ,\times )}$에는 $x{\displaystyle }$ ${\displaystyle \cdot y}$ = ${\displaystyle {}^{}}$ ⋅ ${\displaystyle y^{}}$ = x ${\$가 부여한 올바른 동작$($ ,${\displaystyle }$⋅ ) ${\mathb {N},$ {n$},\$$cdot$ $)$이 있다$$$.$

변환 세미그룹

변환 세미그룹과 세미그룹 활동 사이의 대응은 아래에 설명되어 있다.만약 우리가 그것을 충실한 세미그룹 활동으로 제한한다면, 그것은 좋은 속성을 가지고 있다.

어떤 변환 세미그룹도 다음과 같은 구성에 의해 세미그룹 작용으로 바뀔 수 있다.For any transformation semigroup ${\displaystyle S}$ of ${\displaystyle X}$, define a semigroup action ${\displaystyle T}$ of ${\displaystyle S}$ on ${\displaystyle X}$ as ${\displaystyle T(s,x)=s(x)}$ for ${\displaystyle s\in S,x\in X}$. This action is faithful($c{\displaystyle }$ ${\displaystyle u}$ r ${\displaystyle y}$( T${\displaystyle }$) ${\displaystyle curry(T)}$이(가) 주입되는$$ 것과 같다.

Conversely, for any semigroup action ${\displaystyle T}$ of ${\displaystyle S}$ on ${\displaystyle X}$, define a transformation semigroup ${\displaystyle S'=\{T_{s}\mid s\in S\}}$. In this construction we "forget" the set ${\displaystyle S}$. ${\displaystyle S'}$ is equal$c{\displaystyle }$ ${\displaystyle u}$ r ${\displaystyle y}$( T${\displaystyle }$) ${\displaystyle curry(T)}$의 이미지에 대해$.$ $c{\displaystyle }$ ${\displaystyle u}$ ${\displaystyle r}$ y ${\displaystyle (T}$)$${\$displaystyle curry(T)}$을(를) $f{\displaystyle }${\$displaystyle f}$로 표시하여$$ 간결하게 하자.$f{\displaystyle }$ ${\displaystyle f}$이(가) 주입식이라면 $S{\displaystyle }$ ${\displaystyle S}$에서 $S{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$까지의 세미그룹 이형성$.$ 즉, $T{\displaystyle }$ ${\displaystytle T}$이(가) 충실하다면$$ 중요한 것을 잊어버리는 것이다.This claim is made precise by the following observation: if we turn ${\displaystyle S'}$ back into a semigroup action ${\displaystyle T'}$ of ${\displaystyle S'}$ on ${\displaystyle X}$, then ${\displaystyle T'(f(s),x)=T(s,x)}$ for all ${\displ$$aystyle s\in S,x\in$ X$\}.$ T ${\displaystyle T}$과 $\$ {\$displaystyle$ T$'}$은$$f {\$displaystyle f$ 즉, 우리는 본질적으로 T ${\displaystytle T}$을(를$)$ 통해 "이형식"이므로$$ 일부 저자는^[3] 충실한 의미군 간의 구분이 없다고 본다.

컴퓨터 과학에 대한 응용 프로그램

세미우토마타

변환 세미그룹은 오토마타 이론에서 유한 상태 기계의 구조 이론에 필수적이다.특히 반유토마톤은 트리플(,,X,T)으로 여기서 σ은 입력 알파벳이라 불리는 비빈 집합, X는 상태 집합이라 불리는 비빈 집합, T는 함수다.

$\displaystyle T\colon \Sigma \time X\to X}$

전환함수라고 불린다.세미우토마타는 초기 상태와 수용 상태의 집합을 무시함으로써 결정론적 자동자에서 발생한다.

반유토마톤이 주어지면 let_a σ에 대해 T: X → X가 T(x_a) = T(a,x)로 정의된 X의 변형을 나타내도록 한다.그 다음, {T_a : } }}에 의해 생성된 X의 변환의 세미그룹을 (σ, X, T)의 특성 세미그룹 또는 전환체계라고 부른다.이 세미그룹은 모노이드여서, 이 모노이드를 특성 또는 전이 모노이드라고 부른다.또한 X에서는 σ-act로^∗ 보기도 하는데, 여기서 σ은^∗ 알파벳 σ에 의해 생성되는 문자열의 자유로운 단조형이며,^{[note 1]} 문자열의 작용은 속성을 통해 σ의 작용을 확장한다.

${\displaystyle T_{vw}=T_{w}\circule T_{v}}}$

크론-로즈 이론

Krohn-Rodes 이론은 대수 자동 이론이라고도 불리며, 유한 변환 세미그룹에 대해 더 단순한 요소들을 계단식으로 배열함으로써 강력한 분해 결과를 제공한다.

메모들

참조

• A. H. 클리퍼드와 G. B. 프레스턴(1961), 셈그룹의 대수학 이론, 제1권.미국 수학 협회, ISBN 978-0-8218-0272-4
• A. H. 클리퍼드와 G. B. 프레스턴(1967), 세미그룹의 대수학 이론, 제2권.미국 수학 협회, ISBN 978-0-8218-0272-4
• 마티 킬프, 울리히 크나워, 알렉산더 5세Mikhalev(2000), Monoids, Acts and Categories: Hward Products and Graphs, Expositions in Mathical 29, Walter de Gruyter, ISBN 978-3-11-015248-7.
• 루돌프 리들 및 귄터 필즈, 응용 추상 대수(1998), 스프링어, ISBN 978-0-387-98290-8