인식 가능한 집합

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "인식 가능한 세트" – 뉴스 · 신문 · 책 · 학자 · JSTOR(2021년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

컴퓨터 과학에서, 오토마타 이론에서 보다 정확히 말하면, 인식 가능한 모노이드 집합은 유한한 모노이드에 대한 어떤 형태론에 의해 구별될 수 있는 부분집합이다.인지할 수 있는 집합은 오토마타 이론, 공식 언어, 대수학에서 유용하다.

이 개념은 인식 가능한 언어의 개념과는 다르다.실제로, "인식 가능한"이라는 용어는 계산가능성 이론에서 다른 의미를 갖는다.

정의

Let ${\displaystyle N}$ be a monoid, a subset ${\displaystyle S\subseteq N}$ is recognized by a monoid ${\displaystyle M}$ if there exists a morphism ${\displaystyle \phi }$ from ${\displaystyle N}$ to ${\displaystyle M}$ such that ${\displaystyle S=\phi ^{-1}(\phi ($$S$ 그리고 그것이 어떤 유한한 모노이드에 의해 인식되는 경우 알아볼 수 있다.This means that there exists a subset ${\displaystyle T}$ of ${\displaystyle M}$ (not necessarily a submonoid of ${\displaystyle M}$) such that the image of ${\displaystyle S}$ is in ${\displaystyle T}$ and the image of ${\displaystyle N\setminus S}$ is in ${\displaystyle M\setminus T$$}$.

예

${\displaystyle A}$을(를) $알파벳$으로 두십시오. ${\displaystyle A}$ $위$에 있는 단어 A ${\displaystyle {\ast }^{}}${\$displaystyle A^{*}}$은(는) 단조형이며$$, $A{\displaystyle }$ ${\displaystystyle A}$에 있는 자유 모노이드입니다$.$$∗{\$의 인식 가능한 하위 집합이 정확히 정규어다.실제로 그러한 언어는 언어를 인식하는 어떤 자동화의 전환 단조로움으로 인식된다.

$N{\displaystyle \mathbb{}}$ ${\$의 인식 가능한 하위 집합은 궁극적으로$$ 주기적인 정수 집합이다.

특성.

$N{\displaystyle }$ ${\displaystyle N}$의 하위 집합은 해당 구문 단모형이 유한한 경우에만 인식할 수 있다$$.

$N{\displaystyle }$ ${\displaystyle N}$의 인식 가능한 하위 집합의$$ R ${\displaystyle \mathrm{E}}$ ${\displaystyle \mathrm{C}}$(${\displaystyle N}$) ${\displaystyle \matrm {REC}(N)$ 집합은 다음과 같이 닫힌다$$.

• 결합하다
• 교차로
• 보완하다
• 좌우 시세

폼의 하위 집합 R1×⋯×Rn{\displaystyle R_{1}\times \cd의, 그것이 한정된 노조 메차이의 theorem[표창 필요한]보고서는 monoids M1,…만약 M{M\displaystyle}은 제품, Mn{\displaystyle M_{1},\dots ,M_{n}}, 그때 M{M\displaystyle}부분 집합을 알아볼 수 있다.ots R_{n}\times}$$, 여기서 각 ${\displaystyle {Ri}_{}}$ ${\$은(는) ${\displaystyle {Mi}_{}}$ ${\$의 인식 가능한 부분 집합입니다${\displaystyle .<img\; alt="M\_\{i\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/eda8fd06f1cd5de22ed07385a0f8aa19773b2de9"\; style="vertical-align:\; -0.671ex;\; width:3.054ex;\; height:2.509ex;"\; papago-attr-id="118">}$ 예를 들어, $N{\displaystyle \mathbb{}}$ ${\$ $\mathb$ {$N$$}$의 ${\displaystyle \mathrm{부분}}$ 집합 $\{{\displaystyle }$1$$}{1$\displaystystystyle$ $\mathb${N$$$}$은 합리적이고 따라서 인식할 수 있다.$N{\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {\mathrm{}}^{}}$ ${\$의 $부분집합{\displaystyle }$ S${\displaystyle }$=${\displaystyle }${${\displaystyle }$( ${\displaystyle 1}$,${\displaystyle 1}$)${\displaystyle \}}${\$displaystyle$ S$=\(1,1)\}\}}}$을(를) 인식할 수 있는$$ 것으로 뒤따른다.

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

반대로 $N{\displaystyle }$ ${\displaystyle N}$이(가) 정밀하게 생성되더라도$$ 합리적인 부분 집합을 인식할 수 없을 수 있다.사실, $N{\displaystyle }$ ${\displaystyle N}$의 유한 부분 집합이라도 반드시 알아볼 수 있는 것은 아니다$$.For instance, the set ${\displaystyle \{0\}}$ is not a recognizable subset of ${\displaystyle (\mathbb {Z} ,+)}$. Indeed, if a morphism ${\displaystyle \phi }$ from ${\displaystyle \mathbb {Z} }$ to ${\displaystyle M}$ satisfies ${\displaystyle \{0\}=\ph$$^{-1}(\phi(\{0$ 그러면 $\varphi {\displaystyle }$ ${\displaystyle \pi }}$이(가) 주입 함수이므로 $M{\displaystyle }$ ${\displaystyle M}$은(는) 무한하다.

또한 일반적으로 $R{\displaystyle \mathrm{}}$ ${\displaystyle \mathrm{E}}$ ${\displaystyle \mathrm{C}}$( ${\displaystyle N}$) ${\displaystyle \mathrm {REC} (N)}$은(는) 클레네 별 아래 닫히지 않는다$$.For instance, the set ${\displaystyle S=\{(1,1)\}}$ is a recognizable subset of ${\displaystyle \mathbb {N} ^{2}}$, but ${\displaystyle S^{*}=\{(n,n)\mid n\in \mathbb {N} \}}$ is not recognizable.사실, 그것의 통사적 단모형은 무한하다.

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

인식 가능한 집합은 형태론의 역순으로 닫힌다.I.e. if ${\displaystyle N}$ and ${\displaystyle M}$ are monoids and ${\displaystyle \phi :N\rightarrow M}$ is a morphism then if ${\displaystyle S\in \mathrm {REC} (M)}$ then ${\displaystyle \phi ^{-1}(S)=\{x\mid \phi (x)\in S\}\in \m$$atsrm {REC}(N)}$.

유한집단의 경우 Anissimov와 Seifert의 다음 결과는 잘 알려져 있다: H가 G에 유한지수를 가지고 있는 경우에만 미세하게 생성된 그룹 G의 부분군 H를 인식할 수 있다.반대로 H는 H가 미세하게 생성될 경우에만 합리적이다.^[1]

참고 항목

• 이성 집합
• 이성 단면체

참조

• 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장: 인식 가능하고 합리적인 집합

추가 읽기

• 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.