Monóide livre - Free monoid

Na álgebra abstrata , o monóide livre em um conjunto é o monóide cujos elementos são todas as sequências finitas (ou strings) de zero ou mais elementos desse conjunto, com a concatenação de strings como operação monóide e com a sequência única de zero elementos, muitas vezes chamada de string vazia e denotada por ε ou λ, como o elemento de identidade . O monóide livre em um conjunto A é geralmente denotado A ^∗ . O semigrupo livre em A é o sub semigrupo de A ^∗ contendo todos os elementos exceto a string vazia. Geralmente é denotado como A ⁺ .

Mais geralmente, um monóide abstrato (ou semigrupo) S é descrito como livre se for isomorfo ao monóide livre (ou semigrupo) em algum conjunto.

Como o nome indica, monóides e semigrupos livres são aqueles objetos que satisfazem a propriedade universal usual definindo objetos livres , nas respectivas categorias de monóides e semigrupos. Segue-se que todo monóide (ou semigrupo) surge como uma imagem homomórfica de um monóide (ou semigrupo) livre. O estudo de semigrupos como imagens de semigrupos livres é denominado teoria combinatória de semigrupos.

Monóides livres (e monóides em geral) são associativos , por definição; ou seja, eles são escritos sem parênteses para mostrar o agrupamento ou ordem de operação. O equivalente não associativo é o magma livre .

Exemplos

Números naturais

O monóide ( N ₀ , +) dos números naturais (incluindo zero) sob adição é um monóide livre em um gerador livre singleton, neste caso o número natural 1. De acordo com a definição formal, este monóide consiste em todas as sequências como "1 "," 1 + 1 "," 1 + 1 + 1 "," 1 + 1 + 1 + 1 "e assim por diante, incluindo a sequência vazia. Mapear cada uma dessas sequências para seu resultado de avaliação e a sequência vazia para zero estabelece um isomorfismo do conjunto de tais sequências para N ₀ . Este isomorfismo é compatível com o "+", isto é, para quaisquer duas sequências de s e t , se s é mapeado (isto é avaliada) para um número de m e t a n , em seguida, a concatenação s + t é mapeada para a soma m + n .

Estrela de Kleene

Na teoria da linguagem formal , geralmente um conjunto finito de "símbolos" A (às vezes chamado de alfabeto) é considerado. Uma sequência finita de símbolos é chamada de "palavra sobre A ", e o monóide livre A ^∗ é chamado de " estrela Kleene de A ". Assim, o estudo abstrato de linguagens formais pode ser pensado como o estudo de subconjuntos de monóides livres gerados finitamente.

Por exemplo, assumindo um alfabeto A = { a , b , c }, sua estrela de Kleene A ^∗ contém todas as concatenações de a , b e c :

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

Se A for qualquer conjunto, a função de comprimento de palavra em A ^∗ é o homomorfismo monóide único de A ^∗ a ( N ₀ , +) que mapeia cada elemento de A para 1. Um monóide livre é, portanto, um monóide graduado . (Um monóide graduado é um monóide que pode ser escrito como . Cada um é um grau; a graduação aqui é apenas o comprimento da string. Isto é, contém aquelas strings de comprimento. O símbolo aqui pode ser interpretado como "união de conjuntos"; é usado em vez do símbolo porque, em geral, as uniões definidas podem não ser monóides e, portanto, um símbolo distinto é usado. Por convenção, as gradações são sempre escritas com o símbolo.) ${\ displaystyle M}$${\ displaystyle M = M_ {0} \ oplus M_ {1} \ oplus M_ {2} \ cdots}$${\ displaystyle M_ {n}}$${\ displaystyle M_ {n}}$${\ displaystyle n.}$${\ displaystyle \ oplus}$${\ displaystyle \ cup}$${\ displaystyle \ oplus}$

Existem conexões profundas entre a teoria dos semigrupos e a dos autômatos . Por exemplo, toda linguagem formal tem um monóide sintático que reconhece essa linguagem. Para o caso de uma linguagem regular , esse monóide é isomorfo ao monóide de transição associado ao semiautomático de algum autômato finito determinístico que reconhece aquela linguagem. As linguagens regulares sobre um alfabeto A são o fechamento dos subconjuntos finitos de A *, o monóide livre sobre A, sob união, produto e geração de submonóide.

Para o caso de computação concorrente , ou seja, sistemas com bloqueios , mutexes ou junções de thread , a computação pode ser descrita com monóides de histórico e monóides de rastreamento . A grosso modo, os elementos do monóide podem comutar (por exemplo, threads diferentes podem ser executados em qualquer ordem), mas apenas até um bloqueio ou mutex, que evita comutação adicional (por exemplo, serializar o acesso de thread a algum objeto).

Palavras conjugadas

Exemplo para o primeiro caso de equidivisibilidade: m = "UNCLE", n = "ANLY", p = "UN", q = "CLEANLY" e s = "CLE"

Definimos um par de palavras em A ^∗ da forma uv e vu como conjugado : os conjugados de uma palavra são, portanto, seus deslocamentos circulares . Duas palavras são conjugado neste sentido se forem conjugado no sentido da teoria de grupos como elementos do grupo livre gerado por A .

Equidivisibilidade

Um monóide livre é equidivisível : se a equação mn = pq for válida, então existe um s tal que m = ps , sn = q (veja o exemplo na imagem) ou ms = p , n = sq . Esse resultado também é conhecido como lema de Levi .

Um monóide é livre se e somente se for graduado e equidivisível.

Geradores e classificação grátis

Os membros de um conjunto A são chamados de geradores livres para A ^∗ e A ⁺ . O sobrescrito * é então comumente entendido como a estrela de Kleene . Mais geralmente, se S é um monóide livre abstrato (semigrupo), então um conjunto de elementos que mapeiam no conjunto de palavras de uma única letra sob um isomorfismo para um semigrupo A ⁺ (monóide A ^∗ ) é chamado de um conjunto de geradores livres para S .

Cada semigrupo livre (ou monoid) S tem exatamente um conjunto de geradores livres, a cardinalidade do que é chamado de classificação da S .

Dois monóides ou semigrupos livres são isomórficos se e somente se eles têm a mesma classificação. Na verdade, cada conjunto de geradores para um semigrupo livre ou monóide S contém os geradores livres (ver definição de geradores em Monoid ), uma vez que um gerador livre tem comprimento de palavra 1 e, portanto, só pode ser gerado por ele mesmo. Segue-se que um semigrupo ou monóide livre é finitamente gerado se e somente se tiver uma classificação finita.

Um submonoid N de A ^* é estável se u , v , ux , xv em N em conjunto implica x em N . Um submonóide de A ^∗ é estável se e somente se estiver livre. Por exemplo, usando o conjunto de bits {"0", "1"} como A , o conjunto N de todas as sequências de bits contendo um número par de "1" s é um submonóide estável porque se u contém um número par de "1 "s e ux também, então x deve conter um número par de" 1 "s também. Embora N não possa ser gerado livremente por qualquer conjunto de bits únicos, ele pode ser gerado livremente pelo conjunto de sequências de bits {"0", "11", "101", "1001", "10001", ...} - o conjunto de cadeias de caracteres da forma "10 ⁿ 1" para algum inteiro n .

Códigos

Um conjunto de geradores livres para um monóide livre P é referido como uma base para P : um conjunto de palavras C é um código se C * for um monóide livre e C for uma base. Um conjunto X de palavras em A ^∗ é um prefixo , ou tem a propriedade prefix , se não contiver um prefixo (string) próprio de nenhum de seus elementos. Cada prefixo em A ⁺ é um código, na verdade um código de prefixo .

Um submonoid N de A ^* é unitária direita se x , xy em N implica y em N . Um submonóide é gerado por um prefixo se, e somente se, for unitário correto.

Fatoração

A fatoração de um monóide livre é uma sequência de subconjuntos de palavras com a propriedade de que cada palavra no monóide livre pode ser escrita como uma concatenação de elementos extraídos dos subconjuntos. O teorema de Chen-Fox-Lyndon afirma que as palavras de Lyndon fornecem uma fatoração. De maneira mais geral, as palavras de Hall fornecem uma fatoração; as palavras de Lyndon são um caso especial das palavras de Hall.

Casco livre

A intersecção de submonóides livres de um monóide livre A ^∗ é novamente livre. Se S é um subconjunto de um monóide livre A *, então a interseção de todos os submonóides livres de A * contendo S é bem definida, uma vez que o próprio A * é livre e contém S ; é uma monoid livre e chamou o casco livre de S . Uma base para essa interseção é um código.

O teorema do defeito afirma que se X é finito e C é a base do casco livre de X , então X é um código e C = X , ou

| C | ≤ | X | - 1.

Morfismos

Um morfismo monóide f de um monóide livre B ^∗ para um monóide M é um mapa tal que f ( xy ) = f ( x ) ⋅ f ( y ) para as palavras x , y e f (ε) = ι, onde ε e ι denota o elemento de identidade de B ^∗ e M , respectivamente. O morfismo f é determinado por seus valores nas letras de B e, inversamente, qualquer mapa de B a M se estende a um morfismo. Um morfismo é não apagável ou contínuo se nenhuma letra de B mapear para ι e trivial se todas as letras de B mapearem para ι.

Um morfismo f de um monóide livre B ^∗ para um monóide livre A ^∗ é total se todas as letras de A ocorrerem em alguma palavra na imagem de f ; cíclico ou periódico se a imagem de f estiver contida em { w } ^∗ para alguma palavra w de A ^∗ . Um morfismo f é k -uniforme se o comprimento | f ( a ) | é constante e igual a k para todos um em um . Um morfismo uniforme 1 é estritamente alfabético ou uma codificação .

Um morfismo f de um monóide livre B ^∗ para um monóide livre A ^∗ é simplificável se houver um alfabeto C de cardinalidade menor que o de B tal o morfismo f fatore através de C ^∗ , ou seja, é a composição de um morfismo de B ^∗ para C ^∗ e um morfismo deste para A ^∗ ; caso contrário, f é elementar . O morfismo f é chamado de código se a imagem do alfabeto B sob f for um código: todo morfismo elementar é um código.

Conjuntos de teste

Para G um subconjunto de B ^* , um subconjunto finito T de G é um conjunto de teste para G se morphisms de f e g de B ^* concordam em L , se e apenas se eles concordam em T . A conjectura de Ehrenfeucht é que qualquer subconjunto L tem um conjunto de teste: ele foi provado independentemente por Albert e Lawrence; McNaughton; e Guba. As provas contam com o teorema da base de Hilbert .

Mapear e dobrar

A modalidade computacional de um morfismo monóide é um mapa seguido por uma dobra . Nesta configuração, o monóide livre em um conjunto A corresponde a listas de elementos de A com concatenação como a operação binária. Um homomorfismo monóide do monóide livre para qualquer outro monóide ( M , •) é uma função f tal que

• f ( x ₁ ... x _n ) = f ( x ₁ ) • ... • f ( x _n )
• f () = e

onde e é a identidade em M . Computacionalmente, todo homomorfismo corresponde a uma operação de mapa aplicando f a todos os elementos de uma lista, seguida por uma operação de dobra que combina os resultados usando o operador binário •. Este paradigma computacional (que pode ser generalizado para operadores binários não associativos) inspirou a estrutura do software MapReduce .

Endomorfismos

Um endomorfismo de A ^∗ é um morfismo de A ^∗ para si mesmo. O mapa de identidade I é um endomorfismo de A ^∗ , e os endomorfismos formam um monóide sob composição de funções .

Um endomorfismo f é prolongável se houver uma letra a tal que f ( a ) = como para uma string não vazia s .

Projeção de cordas

A operação de projeção da corda é um endomorfismo. Ou seja, dada uma letra a ∈ Σ e uma string s ∈ Σ ^∗ , a projeção da string p _a ( s ) remove todas as ocorrências de a de s ; é formalmente definido por

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

Observe que a projeção das cordas é bem definida, mesmo se a classificação do monóide for infinita, pois a definição recursiva acima funciona para todas as cordas de comprimento finito. A projeção das cordas é um morfismo na categoria dos monóides livres, de modo que

${\ displaystyle p_ {a} \ left (\ Sigma ^ {*} \ right) = \ left (\ Sigma -a \ right) ^ {*}}$

onde é entendido como o monóide livre de todas as cadeias finitas que não contêm a letra a . A projeção comuta com a operação de concatenação de string, de modo que para todas as strings s e t . Existem muitos inversos corretos para a projeção de cordas e, portanto, é um epimorfismo dividido . ${\ displaystyle p_ {a} \ left (\ Sigma ^ {*} \ right)}$${\ displaystyle p_ {a} (st) = p_ {a} (s) p_ {a} (t)}$

O morfismo de identidade é definido como para todas as strings s , e . ${\ displaystyle p _ {\ varepsilon},}$${\ displaystyle p _ {\ varepsilon} (s) = s}$${\ displaystyle p _ {\ varepsilon} (\ varepsilon) = \ varepsilon}$

A projeção da corda é comutativa, tão claramente

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

Para monóides livres de classificação finita, isso decorre do fato de que monóides livres da mesma classificação são isomórficos, pois a projeção reduz a classificação do monóide em um.

A projeção da corda é idempotente , pois

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

para todas as strings s . Assim, a projeção é uma operação idempotente e comutativa e, portanto, forma uma semilática limitada ou uma banda comutativa .

O monóide comutativo grátis

Dado um conjunto A , o monóide comutativo livre em A é o conjunto de todos os multisets finitos com elementos retirados de A , com a operação monoidal sendo a soma multiset e a unidade monóide sendo o multiset vazio.

Por exemplo, se A = { a , b , c }, os elementos do monóide comutativo livre em A são da forma

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

O teorema fundamental da aritmética afirma que o monóide de inteiros positivos sob multiplicação é um monóide comutativo livre em um conjunto infinito de geradores, os números primos .

O semigrupo comutativo livre é o subconjunto do monóide comutativo livre que contém todos os multiconjuntos com elementos retirados de A, exceto o multiconjunto vazio.

O monóide parcialmente comutativo livre , ou traço de monóide , é uma generalização que engloba os monoides comutativos livres e livres como instâncias. Essa generalização encontra aplicações em combinatória e no estudo de paralelismo em ciência da computação .

Veja também

• Operações de string

Notas

Referências

• 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, 129 , Cambridge: Cambridge University Press , ISBN 978-0-521-88831-8, Zbl  1187.94001
• Lothaire, M. (1997), Combinatorics on words , Cambridge Mathematical Library, 17 , Colaboradores: Perrin, D .; Reutenauer, C .; Berstel, J .; Pin, JE; Pirillo, G .; Foata, D .; Sakarovitch, J .; Simon, I .; Schützenberger, MP; Choffrut, C .; Cori, editores da R. Series: Lyndon, Roger; Rota, Gian-Carlo. Prefácio de Roger Lyndon (2ª 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, 90 , com prefácio de Jean Berstel e Dominique Perrin (Reimpressão da edição de capa dura de 2002), Cambridge University Press , ISBN 978-0-521-18071-9, Zbl  1221.68183
• Lothaire, M. (2005), Aplicada combinatória em palavras , Enciclopédia de Matemática e suas Aplicações, 105 , Uma obra coletiva de 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 e 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, cristão; Siegel, A. (eds.), Substitutions in dynamics, arithmetics and combinatorics , Lecture Notes in Mathematics, 1794 , Berlin: Springer-Verlag , ISBN 3-540-44141-7, Zbl  1014.11015
• Sakarovitch, Jacques (2009), Elementos da teoria dos autômatos , traduzido do francês por 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

links externos

• Mídia relacionada ao monóide livre no Wikimedia Commons