프리 모노이드

추상 대수학에서, 집합의 자유 모노이드(free monoid)는 그 집합으로부터 0개 이상의 원소들의 모든 유한 시퀀스(또는 문자열)인 모노이드로, 단조 연산으로서 끈 연결 및 0 원소의 고유 시퀀스와 함께 종종 빈 문자열이라 불리며, ε 또는 λ으로 표시된다. A 세트에 있는 자유 모노이드는 보통^∗ A로 표시된다. A의 자유 세미그룹은 빈 문자열을 제외한 모든 요소를 포함하는 A의^∗ 하위 그룹이다. 보통 A로⁺ 표기된다.^[1][2]

보다 일반적으로 추상적인 모노이드(또는 세미그룹) S는 일부 집합에서 자유 모노이드(또는 세미그룹)에 대해 이형인 경우 자유라고 기술된다.^[3]

이름에서 알 수 있듯이, 자유 모노이드와 세미그룹은 각각의 모노이드와 세미그룹의 범주에서 자유 객체를 정의하는 일반적인 보편적 특성을 만족하는 개체들이다. 따라서 모든 모노이드(또는 세미그룹)는 자유 모노이드(또는 세미그룹)의 동형상 이미지로 발생한다. 자유 세미그룹의 이미지로서 세미그룹을 연구하는 것을 콤비네이터 세미그룹 이론이라고 한다.

자유 모노이드(및 일반적으로 모노이드)는 정의상 연관성이 있다. 즉, 그것들은 그룹화 또는 작동 순서를 나타내기 위해 괄호 없이 쓰여진다. 연관성이 없는 등가는 자유 마그마이다.

예

자연수

추가적으로 자연수(0을 포함)의 모노이드(N₀,+)는 1톤 자유 발전기의 자유 단모형이며, 이 경우 자연수 1이다. 형식 정의에 따르면 이 모노이드에는 빈 시퀀스를 포함하여 "1", "1+1", "1+1+1", "1+1+1" 등과 같은 모든 시퀀스로 구성된다. 이러한 각 시퀀스를 평가 결과와 0에 매핑하면 그러한 시퀀스의 집합에서 N에₀ 이르는 이형성이 확립된다. 이 이형성은 "+", 즉 어떤 두 시퀀스 s와 t에 대해 s가 숫자 m과 t에서 n에 매핑(즉, 평가)되면 이들의 결합 s+t가 합 m+n에 매핑된다.

클레인 항성

형식 언어 이론에서는 보통 "기호" A(가끔 알파벳이라고도 함)의 유한 집합이 고려된다. 기호들의 유한순서는 "A보다 단어"라고 불리며, 자유 모노이드 A는^∗ "A의 클레인 스타"라고 불린다. 따라서 형식 언어에 대한 추상적인 연구는 미세하게 생성된 자유 모노이드의 하위 집합에 대한 연구라고 생각할 수 있다.

예를 들어, 알파벳 A = {a, b, c}을(를) 가정할 때, 클레인 별^∗ A는 a, b, c의 모든 연결을 포함한다.

{ε, a, ab, ba, cccbabbc, ...}

만약 A가 어떤 세트라면, A의^∗ 단어 길이 함수는^∗ A에서 (N₀,+)까지의 고유한 단성 동형성으로서 A의 각 원소를 1로 맵핑하는 것이다. 자유로운 모노이드는 따라서 등급이 매겨진 모노이드다.^[5] (A graded monoid ${\displaystyle M}$ is a monoid that can be written as ${\displaystyle M=M_{0}\oplus M_{1}\oplus M_{2}\cdots }$. Each ${\displaystyle M_{n}}$ is a grade; the grading here is just the length of the string. 즉, $M{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$은(는) 길이 $n{\displaystyle }$. {\$displaystyle$ n$.}$의 문자열을 포함한다$$.$$ 여기서 $\oplus {\displaystyle }$ ${\displaystyle \oplus }$ 기호는$$ "set union"을 의미하는 것으로 해석할 수 있으며, 일반적으로$$ 세트 유니언은 모노이드(monoid)가 아닐 수 있으므로 $\cup {\displaystyle }$ ${\displaysty \cup$ \cup $}$ 기호 대신 사용된다. 관례에 따라 등급은 항상${\displaystyle }$⊕ ${\displaystyle \oplus }$ 기호로$$ 기록된다.

세미그룹 이론과 오토마타 이론 사이에는 깊은 연관성이 있다. 예를 들어, 모든 공식언어는 그 언어를 인식하는 통사적 단모형을 가지고 있다. 정규 언어의 경우, 그 모노이드(monoid)는 그 언어를 인식하는 어떤 결정론적 유한 자동화의 반유토마톤과 연관된 전이 단모형(transition monoid)과 이형(異形)이다. 알파벳 A에 대한 정규어는 A*의 유한 부분 집합, A에 대한 자유 모노이드, 결합, 제품 및 서브모노이드 생성의 폐쇄다.^[6]

동시 계산의 경우, 즉 잠금장치, 뮤텍스 또는 스레드 결합이 있는 시스템의 경우, 이력 모노이드 및 추적 모노이드로 연산을 설명할 수 있다. 대략적으로 말하면, 모노이드의 요소들은 통근할 수 있지만(예: 다른 나사산은 어떤 순서로도 실행될 수 있다), 더 이상의 분류를 방지하는 잠금 장치나 뮤텍스까지만 통근할 수 있다(예: 어떤 물체에 대한 스레드 접근을 직렬화).

공자어

우리는 uv와 vu의 A형에서^∗ 한 쌍의 단어를 결합으로 정의한다: 단어의 결합은 따라서 그 원형의 이동이다.^[7] A에 의해 생성되는 자유집단의 요소로서 집단이론의 의미에서의 결합이라면 이 의미에서는 두 단어가 결합된다.^[8]

동일시성

자유 모노이드(free monoid)는 등식 mn = pq가 유지되면 m = ps, sn = q(예: 이미지 보기) 또는 ms = p, n = sq와 같은 s가 존재한다.^[9] 이 결과는 Levi의 보조정리라고도 알려져 있다.^[10]

모노이드는 등급이 매겨지고 분리될 수 없는 경우에만 자유롭다.^[9]

자유 생성기 및 순위

A 세트의 멤버는 A와^∗ A의⁺ 프리 제너레이터라고 불린다. 위첨자 *는 일반적으로 클레인 항성으로 이해된다. 보다 일반적으로 S가 추상적인 자유형 단수형(세미그룹)이라면⁺, 이소형성(semography A^∗)에 따른 단문자 집합에 매핑되는 원소 집합을 S를 위한 자유형 발전기 집합이라고 한다.

각 자유 세미그룹(또는 단일체) S는 정확히 하나의 자유 생성기를 가지고 있는데, 이 세트의 카디널리티를 S의 순위라고 부른다.

두 개의 자유 모노이드 또는 세미그룹들은 같은 순위를 가진 경우에만 이등형이다. 사실, 자유 발전기는 단어 길이 1을 가지고 있기 때문에, 자유 세미그룹이나 모노이드 S의 모든 발전기 집합은 자유 발전기를 포함한다(모노이드의 발전기 정의 참조). 자유 세미그룹이나 모노이드는 순위가 유한한 경우에만 정밀하게 생성된다.

A의^∗ 서브모노이드 N은 N의 u, v, ux, xv가 함께 x를 의미할 경우 안정적이다.^[11] A의^∗ 서브모노드는 자유일 경우에만 안정적이다.^[12] 예를 들어 비트 { "0", "1" } 집합을 A로 사용하면 짝수 숫자 "1"을 포함하는 모든 비트 문자열의 N 집합은 안정적인 서브모노이드로서, u가 짝수 숫자 "1"과 ux를 포함하는 경우 x도 짝수 숫자 "1"을 포함해야 하기 때문이다. N은 어떤 단일 비트 집합으로도 자유롭게 생성될 수 없지만, 비트 문자열 집합 { "0", "11", "101", "1001", "10001", ...에 의해 자유롭게 생성될 수 있다. } – 일부 정수 n에 대한 형식 "101ⁿ"의 문자열 집합.

코드

프리 모노이드 P에 대한 프리 제너레이터 집합을 P의 기준으로 언급한다: C*가 프리 모노이드이고 C가 기본이라면 C라는 단어는 코드다.^[3] A에^∗ 있는 단어의 X 집합은 접두사 또는 접두사 속성을 가지며, 그 요소 중 어느 하나의 적절한 (문자열) 접두사를 포함하지 않는 경우. A의⁺ 모든 접두사는 코드, 실로 접두사 코드다.^[3][13]

A의^∗ 서브모노이드 N은 n의 x, xy가 y를 내포하는 경우 우측 단일형이다. 서브모노이드는 우측 단일형인 경우에만 접두사에 의해 생성된다.^[14]

인자화

자유 모노이드의 인자화는 자유 모노이드의 모든 단어가 하위 집합에서 도출된 원소의 결합으로 기록될 수 있는 속성과 함께 단어 하위 집합의 연속이다. 첸-폭스-린든 정리는 린든 단어들이 요소화를 제공한다고 명시하고 있다. 더 일반적으로, 홀 단어는 요소를 제공한다; 린든어는 홀 워드의 특별한 경우다.

자유선체

프리 모노이드 A의^∗ 프리 서브모노이드 교차점이 다시 자유롭다.^[15][16] S가 자유 단모형 A*의 부분 집합체인 경우, A* 자체는 자유롭고 S를 포함하기 때문에, S가 포함된 A*의 모든 자유 서브모노이드의 교차점은 잘 정의되어 있다; 그것은 자유 단모형이며 S의 자유 선체라고 불린다. 이 교차점의 기본은 코드다.

결점 정리에는^[15][16][17] X가 유한하고 C가 X의 자유선체의 기초라면 X는 코드, C = X, 또는 X 중 하나라고 되어 있다.

C ≤ X - 1 .

형태론

자유 모노이드 B에서^∗ 모노이드 M까지의 모노이드 형태론 f는 f(xy) = f(x)⋅f(y) = x,y, f(ε) = ι의 경우 f(x)ff(y) = ι의 지도인데 여기서 b과^∗ of은 각각 B와 M의 정체성 요소를 나타낸다. 형태론 f는 B의 문자에 있는 그것의 값에 의해 결정되며, 반대로 B에서 M까지의 지도는 형태론으로 확장된다. 형태론은 B의 문자가 ι에 매핑되지 않으면 비지연적이거나^[18] 연속적이며^[19], B의 모든 글자가 to에 매핑된다면 사소하다.^[20]

자유단조형^∗ B에서 자유단조형^∗ A까지의 형태론은 A의 모든 글자가 f의 이미지에서 어떤 단어에 발생한다면 총합이고, A의^∗ 어떤 단어 w에 대해 f의 이미지가 {w}^∗에 포함되어 있으면 주기적인^[20] 또는 주기적인^[21] 것이다. 형태론 f는 길이 f(a)가 일정하고 모든 a in A에 대해 k와 같으면 k-uniform이다.^[22][23] 1-통일 형태론은 엄격히 알파벳^[19] 또는 코딩이다.^[24]

자유 모노이드 B에서^∗ 자유 모노이드 A에^∗ 이르는 형태론 f는 카디널리티의 알파벳 C가 C를^∗ 통한 형태론 f 인자들, 즉 그것은^∗ B에서^∗ C로, 그리고 그것에서^∗ A로 형태론의 구성이고, 그렇지 않으면 f는 초등인 경우에 단순화된다. 형태론 f는 f 아래의 알파벳 B의 이미지가 코드라면 코드라고 부른다: 모든 기초 형태론은 코드다.^[25]

테스트 세트

L의 경우^∗, L의 유한 부분 집합 T는, B의^∗ 형태변수 f와 g가 T에 동의하는 경우에만 L에 대한 시험 세트다. Ehrenfeucht 추측에 따르면, 모든 부분집합 L은 알버트와 로렌스, 맥노튼, 그리고 구바에 의해 독립적으로 증명된^[27] 테스트 세트를 가지고 있다.^[26] 그 증거는 힐버트의 기본 정리에 의존한다.^[28]

지도 및 접기

이 절은 출처를 인용하지 않는다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션을 개선할 수 있도록 도와주십시오. 비소싱 소재는 도전하여 제거할 수 있다. (2015년 2월) (이 템플릿 메시지 제거 방법 및 시기 학습)

모노이드 형태론의 계산적 구현은 접힌 지도가 뒤따르는 것이다. 이 설정에서, 세트 A의 자유 모노이드는 이진 연산으로서 결합을 가지는 A의 요소 리스트에 해당한다. 자유단모형에서 다른 단모형(M,•)에 이르는 단모형 동형성은 다음과 같은 함수 f이다.

• f(x₁...x_n) = f(x₁) • … • f(x_n)
• f() = e

여기서 e는 M의 정체성이다. 계산적으로, 그러한 모든 동형성은 목록의 모든 요소에 f를 적용하는 지도 연산에 해당하며, 그 다음에 이진 연산자를 이용한 결과를 결합하는 접기 연산에 해당한다. 이 연산 패러다임(비 연관 바이너리 연산자로 일반화할 수 있음)은 MapReduce 소프트웨어 프레임워크에 영감을 주었다.^{[citation needed]}

내형성

A의^∗ 내형성은 A에서^∗ 그 자체로의 형태론이다.^[29] 아이덴티티 맵 1은 A의^∗ 내형성이며, 내형성은 함수의 구성 아래 단모형을 형성한다.

내형성 f는 f(a) = 비어 있지 않은 문자열 s와 같은 문자가 있는 경우 연장할 수 있다.^[30]

문자열 투영

끈 투영술의 조작은 내형성이다. 즉, 문자 ∈ σ과 문자열 ∈ σ이^∗ 주어지면 문자열 투영_a p(s)는 a에서 발생하는 모든 발생을 s에서 제거하며, 정식으로 정의된다.

${\displaystyle p_{a}(s)={\begin{cases}\varepsilon &{\text{if }}s=\varepsilon ,{\text{ the empty string}}\\p_{a}(t)&{\text{if }}s=ta\\p_{a}(t)b&{\text{if }}s=tb{\text{ and }}b\neq a.\end{case}}}$

위의 재귀적 정의는 유한 길이의 모든 문자열에 대해 작용하므로, 모노이드의 순위가 무한하더라도 문자열 투영은 잘 정의되어 있다는 점에 유의한다. 끈 투영은 자유 모노이드의 범주에 있는 형태론이기 때문에, 다음과 같다.

${\displaystyle p_{a}\왼쪽(\Sigma ^{*}\오른쪽)=\왼쪽(\Sigma -a\오른쪽)^{*}}$

여기서 $p{\displaystyle {}_{}}$ ${\displaystyle {\mathrm{}}^{}}$ (${\displaystyle {}_{}{\ast }^{}}$ )${\$우)는 문자 a를 포함하지 않는 모든 유한 문자열의 자유 단조로 이해된다$.$ 투영은 문자열 연결의 작동에 통근하므로, 모든 문자열 s와 t에$$ ${\displaystyle {대해}_{}}$ p a${\displaystyle {}_{}}$( s${\displaystyle t}$) = ${\displaystyle {}_{}}$ ${\displaystyle a_{}}$ (${\displaystyle s{}_{}}$) ${\displaystyle {}_{}}$ ${\displaystyle a_{}}$ (${\displaystyle {}_{}}$)${\displaystyle p_{a}(st)=p_{a}p_{a}(t)}}.$ 끈 투영에는 많은 오른쪽 반대가 있고, 따라서 그것은 분열된 인식론이다.

The identity morphism is ${\displaystyle p_{\varepsilon },}$ defined as ${\displaystyle p_{\varepsilon }(s)=s}$ for all strings s, and ${\displaystyle p_{\varepsilon }(\varepsilon )=\varepsilon }$.

스트링 투영은 명료하게 대응된다.

${\displaystyle p_{a}(p_{b}s)=p_{b}(p_{a}s).}$

유한 계급의 자유 모노이드의 경우 투영으로 인해 모노이드의 순위가 1개씩 줄어들기 때문에 같은 계급의 자유 모노이드들이 이형성이라는 사실에서 이형성이 나타난 것이다.

문자열 투영은 다음과 같이 idempotent임

${\displaystyle p_{a}(p_{a}s)=p_{a}s}$

모든 방면에서 따라서 투영법은 공증력, 역작용이므로 경계가 있는 반음절 또는 역악대를 형성한다.

자유 정류 단면체

집합 A가 주어진 경우, A의 자유 정류 단면체는 A에서 도출된 원소가 있는 모든 유한 다중값 집합이며, 단면 연산은 다중값 합이고 단면 단위는 빈 다중값이다.

예를 들어, A = {a, b, c}인 경우, A에 있는 자유 정류 모노이드의 요소가 형식이다.

{ε, a, ab, a²b, ab³c⁴, ...}.

산술의 기본 정리는 곱셈에 따른 양의 정수의 단수가 원수인 발전기의 무한 집합에 대한 자유 정류 단수라고 명시한다.

자유 정류 의미 그룹은 비어 있는 멀티셋을 제외하고 A에서 그려진 요소와 함께 모든 멀티셋을 포함하는 자유 정류 단일 그룹의 하위 집합이다.

자유 부분 교환 단면체, 즉 트레이스 단면체(trace monoid)는 예로서 자유 및 자유 정류 단면체 모두를 포괄하는 일반화다. 이 일반화는 결합학에서 응용을 찾고 컴퓨터 과학에서 병렬에 관한 연구를 한다.

참고 항목

• 문자열 연산

메모들

참조

• Allouche, Jean-Paul; Shallit, Jeffrey (2003), Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, ISBN 978-0-521-82332-6, Zbl 1086.11015
• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010), Codes and automata, Encyclopedia of Mathematics and its Applications, vol. 129, Cambridge: Cambridge University Press, ISBN 978-0-521-88831-8, Zbl 1187.94001
• Lothaire, M. (1997), Lothaire, M (ed.), Combinatorics on words, Cambridge Mathematical Library, vol. 17, Contributors: Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R. Series editors: Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon (2nd ed.), Cambridge University Press, doi:10.1017/CBO9780511566097, ISBN 0-521-59924-5, MR 1475463, Zbl 0874.20040
• 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
• Lothaire, M. (2005), Applied combinatorics on words, Encyclopedia of Mathematics and Its Applications, vol. 105, A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé, Cambridge: Cambridge University Press, ISBN 0-521-84802-4, Zbl 1133.68067
• Pytheas Fogg, N. (2002), Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.), Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, vol. 1794, Berlin: Springer-Verlag, ISBN 3-540-44141-7, Zbl 1014.11015
• Sakarovitch, Jacques (2009), Elements of automata theory, Translated from the French by Reuben Thomas, Cambridge: Cambridge University Press, ISBN 978-0-521-84425-3, Zbl 1188.68177
• Salomaa, Arto (1981), Jewels of Formal Language Theory, Pitman Publishing, ISBN 0-273-08522-0, Zbl 0487.68064

외부 링크

• Wikimedia Commons에서 무료 모노이드와 관련된 미디어