이성 집합

컴퓨터 과학에서, 오토마타 이론에서 보다 정확히 말하면, 모노이드의 이성적인 집합은 모든 유한 서브셋을 포함하고 결합, 제품, 클레인 별에 의해 닫히는 이 모노이드의 최소 하위 집합의 한 요소다.이성적인 집합은 오토마타 이론, 공식 언어, 대수학에서 유용하다.

합리적 세트는 합리적(정규적) 언어(정규적 표현으로 정의되는 것으로 이해)의 개념을 반드시 자유롭지 않은 모노이드에 일반화한다.^{[example needed]}

정의

Let${\displaystyle }$( ${\displaystyle N}$, ${\displaystyle \cdot }$) ${\displaystyle (N,\cdot )}$은(는) ID 요소 $e{\displaystyle }$ ${\displaystyle e}$이(가) 있는 단일형입니다$.$$N{\displaystyle }$ ${\displaystyle N}$의 합리적 하위 $집합$의 R A ${\displaystyle \mathrm{T}}$(${\displaystyle N}$ ${\displaystyle )}$ ${\displaystyle \mathrm$ {$RAT}(N)}$ 집합은 모든 유한 집합을 포함하는 최소 집합이며$$, 다음과 같이 닫힌다.

• 유니언: $A{\displaystyle }$, ${\displaystyle B}$ ${\displaystyle \in }$ R ${\displaystyle \mathrm{A}}$ ${\displaystyle \mathrm{T}}$( N${\displaystyle }$) ${\displaystyle A,B\in \matrm {RAT}(N)}$인 경우 $A{\displaystyle }$ ${\displaystyle \cup }$ ${\displaystyle B}$ ${\displaystyle \in }$ R A ${\displaystyle \mathrm{T}}$(${\displaystyle \mathrm{N}}$ ) ${\displaystyle A\cup B\in \matrmatrm {RAT}(N)}$
• product: if ${\displaystyle A,B\in \mathrm {RAT} (N)}$ then ${\displaystyle A\cdot B=\{a\cdot b\mid a\in A,b\in B\}\in \mathrm {RAT} (N)}$
• Kleene star: if ${\displaystyle A\in \mathrm {RAT} (N)}$ then ${\displaystyle A^{*}=\bigcup _{i=0}^{\infty }A^{i}\in \mathrm {RAT} (N)}$ where ${\displaystyle A^{0}=\{e\}}$ is the singleton containing the identity element, and where ${\displaystyle A^{n+1}}$${\displaystyle A^{n+1}=$$A^{n}\cdot A}$.

즉, N ${\$displaystyle N$}$의 유한 부분 집합을 $유한$한 개수의 N {\$displaystyle$N}을(를) 취하여$$ 조합, 제품 및 클레인 항성 연산을 유한한 횟수로 적용함으로써 $N{\displaystyle }$ ${\displaystyle N}$의 합리적인 부분 집합을 얻을 수 있다는$$ 것을 의미한다.

일반적으로 모노이드의 이성적인 부분집합은 하위모노이드가 아니다.

예

${\displaystyle A}$을(를) 알파벳으로 하고, $A{\displaystyle }$ ${\displaystyle A}$ 위에 있는 단어$$ $A{\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}${\$displaystyle$ A$^{*}$을(를) 설정한 것은 단조형이다$$.$∗{\$의 합리적인 부분집합은 정확히 정규어다.실제로 정규어는 유한한 정규식으로 정의될 수 있다.

$N{\displaystyle \mathbb{}}$ ${\$의 합리적 하위 집합은 궁극적으로$$ 주기적인 정수 집합이다.보다 일반적으로 $N{\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$ ${\$의 합리적인 하위 집합은 반선형 집합이다.^[1]

특성.

McKnight의 정리에서는 $N{\displaystyle }$ ${\displaystyle N}$이(가) 미세하게 생성되면$$ 인식 가능한 부분 집합이 이성적인 집합이라고 명시하고 있다.전체 $N{\displaystyle }$ ${\displaystyle N}$은(는) 항상 인식할 수 있지만$$ $N{\displaystyle }$ ${\displaystyle N}$이(가) 무한하게 생성되면 합리적이지 않기 때문에 일반적으로 이는 사실이 아니다.

Rational sets are closed under morphism: given ${\displaystyle N}$ and ${\displaystyle M}$ two monoids and ${\displaystyle \phi :N\rightarrow M}$ a morphism, if ${\displaystyle S\in \mathrm {RAT} (N)}$ then ${\displaystyle \phi (S)=\{\phi (x)\$$mid x\in S\}\in \matrm {RAT}(M$

${\displaystyle \mathrm{R}}$ ${\displaystyle \mathrm{A}}$ ${\displaystyle \mathrm{T}}$( ${\displaystyle N}$) ${\displaystyle \mathrm {RAT}(N)}$은(는) 다음 예에서 보듯이 보완 하에서 닫히지 않는다$$.^[2]Let ${\displaystyle N=\{a\}^{*}\times \{b,c\}^{*}}$, the sets ${\displaystyle R=(a,b)^{*}(1,c)^{*}=\{(a^{n},b^{n}c^{m})\mid n,m\in \mathbb {N} \}}$ and ${\displaystyle S=(1,b{)}^{\ast }(a,c{)}^{\ast }=\{(a^n,b^m}$${\displaystyle S=(1,b)^{*}(a,c)^{*}=\{(a^{n},b^{m}c^{n})\mid n,m\in \mathbb {N} \}}$ are rational but ${\displaystyle R\cap S=\{(a^{n},b^{n}c^{n})\mid n\in \mathbb {N} \}}$ is not because its projection to the second element ${$$\displaystyle \{b^{n}c^{n}\mid n\in \mathb{N}\}}}}$은(는) 합리적이지$$ 않다.

합리적인 부분 집합과 인식 가능한 부분 집합의 교차점은 합리적이다.

유한집단에 대해서는 A의 다음과 같은 결과가 있다.아니시모프와 A. W. 세이퍼트는 잘 알려져 있다: H가 G에 유한 지수를 가지고 있는 경우에만 정밀하게 생성된 G 그룹의 부분군 H를 인식할 수 있다.반대로 H는 H가 미세하게 생성될 경우에만 합리적이다.^[3]

합리적인 관계와 합리적인 기능

M×N의 부분집합으로 간주되는 관계 그래프가 제품 모노이드에서 이성적인 집합이라면 모노이드 M과 N 사이의 이항 관계는 이성적인 관계다.함수의 그래프가 합리적인 집합이라면 M에서 N까지의 함수는 합리적인 함수다.^[4]

참고 항목

• 이성 계열
• 인식 가능한 집합
• 이성 단면체

참조

• Diekert, Volker; Kufleitner, Manfred; Rosenberg, Gerhard; Hertrampf, Ulrich (2016). "Chapter 7: Automata". Discrete Algebraic Methods. Berlin/Boston: Walter de Gruyther GmbH. ISBN 978-3-11-041332-8.
• 장-에릭 핀, 오토마타 이론의 수학적 기초, 제4장: 인식 가능하고 합리적인 집합
• 새뮤얼 에일렌버그와 M. P. 쉬첸베르거, Commutative Monoids의 Rational Sets, Journal of Algebra, 1969.

추가 읽기

• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. Part II: The power of algebra. ISBN 978-0-521-84425-3. Zbl 1188.68177.