Combinatória de palavras - Combinatorics on words

Construção de uma palavra infinita Thue-Morse

Combinatória de palavras é um campo relativamente novo da matemática , ramificando-se da combinatória , que se concentra no estudo de palavras e linguagens formais . O sujeito olha para as letras ou símbolos e as sequências que eles formam. A combinação de palavras afeta várias áreas do estudo matemático, incluindo álgebra e ciência da computação . Tem havido uma ampla gama de contribuições para o campo. Alguns dos primeiros trabalhos foi em palavras-livre quadrados por Axel Thue no início de 1900. Ele e seus colegas observaram padrões nas palavras e tentaram explicá-los. Com o passar do tempo, a combinatória de palavras tornou-se útil no estudo de algoritmos e codificação . Isso levou a desenvolvimentos em álgebra abstrata e respostas a perguntas abertas.

Definição

Combinatória é uma área da matemática discreta . A matemática discreta é o estudo de estruturas contáveis. Esses objetos têm um começo e um fim definidos. O estudo de objetos enumeráveis é o oposto de disciplinas como a análise , onde o cálculo e estruturas infinitas são estudados. A Combinatória estuda como contar esses objetos usando várias representações. Combinatória de palavras é um desenvolvimento recente neste campo que se concentra no estudo de palavras e linguagens formais. Uma linguagem formal é qualquer conjunto de símbolos e combinações de símbolos que as pessoas usam para comunicar informações.

Alguma terminologia relevante para o estudo das palavras deve primeiro ser explicada. Em primeiro lugar, uma palavra é basicamente uma sequência de símbolos, ou letras, em um conjunto finito . Um desses conjuntos é conhecido pelo público em geral como o alfabeto . Por exemplo, a palavra "enciclopédia" é uma sequência de símbolos do alfabeto inglês , um conjunto finito de 26 letras. Visto que uma palavra pode ser descrita como uma sequência, outras descrições matemáticas básicas podem ser aplicadas. O alfabeto é um conjunto , portanto, como seria de se esperar, o conjunto vazio é um subconjunto . Em outras palavras, existe uma palavra única de comprimento zero. O comprimento da palavra é definido pelo número de símbolos que compõem a sequência e é denotado por | w |. Olhando novamente para o exemplo "enciclopédia", | w | = 12, pois a enciclopédia possui doze letras. A ideia de fatoração de grandes números pode ser aplicada a palavras, onde um fator de uma palavra é um bloco de símbolos consecutivos. Assim, "ciclope" é um fator de "enciclopédia".

Além de examinar as sequências em si, outra área a considerar da combinatória em palavras é como elas podem ser representadas visualmente. Em matemática, várias estruturas são usadas para codificar dados. Uma estrutura comum usada em combinatória é a estrutura em árvore . Uma estrutura de árvore é um gráfico onde os vértices são conectados por uma linha, chamada de caminho ou aresta . As árvores podem não conter ciclos e podem ou não ser completas. É possível codificar uma palavra, uma vez que uma palavra é construída por símbolos, e codificar os dados usando uma árvore. Isso dá uma representação visual do objeto.

Principais contribuições

Os primeiros livros de combinatória sobre palavras que resumem as origens do assunto foram escritos por um grupo de matemáticos que, coletivamente, eram chamados de M. Lothaire . Seu primeiro livro foi publicado em 1983, quando a combinatória de palavras se tornou mais difundida.

Padrões

Padrões dentro das palavras

Um dos principais contribuintes para o desenvolvimento da combinatória em palavras foi Axel Thue (1863–1922); ele pesquisou a repetição. A principal contribuição de Thue foi a prova da existência de infinitas palavras sem quadrados . Palavras livres de quadrados não têm fatores repetidos adjacentes. Para esclarecer, "verão" não é livre de quadrados, pois m é repetido consecutivamente, enquanto "enciclopédia" é livre de quadrados. Thue prova sua conjectura sobre a existência de infinitas palavras livres de quadrados usando substituições . Uma substituição é uma forma de pegar um símbolo e substituí-lo por uma palavra. Ele usa essa técnica para descrever sua outra contribuição, a sequência Thue-Morse ou a palavra Thue-Morse.

Thue escreveu dois artigos sobre palavras sem quadrados, o segundo dos quais foi sobre a palavra Thue-Morse. Marston Morse está incluído no nome porque ele descobriu o mesmo resultado que Thue descobriu, mas eles trabalharam de forma independente. Thue também provou a existência de uma palavra sem sobreposição. Uma palavra sem sobreposição ocorre quando, para dois símbolos xey, o padrão xyxyx não existe dentro da palavra. Ele continua em seu segundo artigo para provar uma relação entre palavras sem sobreposição infinitas e palavras sem quadrados. Ele pega palavras sem sobreposição que são criadas usando duas letras diferentes e demonstra como elas podem ser transformadas em palavras sem quadrados de três letras usando a substituição.

Como foi descrito anteriormente, as palavras são estudadas examinando as sequências feitas pelos símbolos. Padrões são encontrados e podem ser descritos matematicamente. Os padrões podem ser evitáveis ou inevitáveis. Um contribuidor significativo para o trabalho de padrões inevitáveis , ou regularidades, foi Frank Ramsey em 1930. Seu importante teorema afirma que para inteiros k, m≥2, existe um número inteiro positivo mínimo R (k, m) tal que, apesar de o gráfico é colorido com duas cores, sempre existirá um subgrafo de cor sólida de cada cor.

Outros contribuintes para o estudo de padrões inevitáveis incluem van der Waerden . Seu teorema afirma que se os inteiros positivos são particionados em k classes, então existe uma classe c tal que c contém uma progressão aritmética de algum comprimento desconhecido. Uma progressão aritmética é uma sequência de números em que a diferença entre os números adjacentes permanece constante.

Ao examinar padrões inevitáveis, os sesquipoderes também são estudados. Para alguns padrões x, y, z, um sesquipower tem a forma x, xyx, xyxzxyx, .... Este é outro padrão, como padrões sem quadrados ou inevitáveis. Coudrain e Schützenberger estudaram principalmente esses sesquipoderes para aplicações da teoria de grupos . Além disso, Zimin provou que os sesquipowers são inevitáveis. Quer o padrão inteiro apareça, ou apenas algum pedaço do sesquipower apareça repetidamente, não é possível evitá-lo.

Padrões dentro de alfabetos

Os colares são construídos a partir de palavras de sequências circulares. Eles são usados com mais frequência na música e na astronomia . Flye Sainte-Marie em 1894 provou que existem 2 ^{2 ^{n −1} - n} colares binários de Bruijn de comprimento 2 ⁿ . Um colar De Bruijn contém fatores feitos de palavras de comprimento n sobre um certo número de letras. As palavras aparecem apenas uma vez no colar.

Em 1874, Baudot desenvolveu o código que viria a tomar o lugar do código Morse , aplicando a teoria dos colares binários de Bruijn. O problema continuou de Sainte-Marie a Martin em 1934, que começou a procurar algoritmos para fazer palavras da estrutura de de Bruijn. Foi então trabalhado por Posthumus em 1943.

Hierarquia de linguagem

Possivelmente, o resultado mais aplicado em combinatória de palavras é a hierarquia de Chomsky , desenvolvida por Noam Chomsky . Ele estudou a linguagem formal na década de 1950. Sua maneira de ver a linguagem simplificou o assunto. Ele desconsidera o significado real da palavra, não considera certos fatores como frequência e contexto e aplica padrões de prazos curtos a todos os termos de comprimento. A ideia básica do trabalho de Chomsky é dividir a linguagem em quatro níveis, ou a hierarquia da linguagem . Os quatro níveis são: normal , livre de contexto , sensível ao contexto , e computably enumerable ou irrestrita. Regular é o menos complexo enquanto computávelmente enumerável é o mais complexo. Embora seu trabalho tenha crescido a partir da combinatória de palavras, afetou drasticamente outras disciplinas, especialmente a ciência da computação .

Tipos de palavras

Palavras sturmianas

As palavras sturmianas , criadas por François Sturm, têm raízes na combinatória das palavras. Existem várias definições equivalentes de palavras sturmianas. Por exemplo, uma palavra infinita é Sturmiana se e somente se ela tiver n + 1 fatores distintos de comprimento n, para cada inteiro não negativo n.

Palavra Lyndon

Uma palavra Lyndon é uma palavra sobre um determinado alfabeto que é escrita em sua forma mais simples e ordenada fora de sua respectiva classe de conjugação . As palavras de Lyndon são importantes porque, para qualquer palavra x de Lyndon, existem palavras de Lyndon y e z, com y <z, x = yz. Além disso, existe um teorema de Chen, Fox e Lyndon , que afirma que qualquer palavra tem uma fatoração única de palavras de Lyndon, em que as palavras de fatoração não são crescentes . Devido a essa propriedade, as palavras de Lyndon são usadas para estudar álgebra , especificamente a teoria dos grupos . Eles formam a base para a ideia de comutadores .

Representação visual

Cobham contribuiu com o trabalho que relaciona o trabalho de Eugène Prouhet com autômatos finitos . Um gráfico matemático é feito de arestas e nós . Com autômatos finitos, as arestas são rotuladas com uma letra do alfabeto. Para usar o gráfico, começa-se em um nó e percorre as arestas para chegar a um nó final. O caminho percorrido ao longo do gráfico forma a palavra. É um grafo finito porque há um número contável de nós e arestas, e apenas um caminho conecta dois nós distintos .

Os códigos de Gauss , criados por Carl Friedrich Gauss em 1838, são desenvolvidos a partir de gráficos. Especificamente, uma curva fechada em um plano é necessária. Se a curva se cruza apenas um número finito de vezes, então rotulamos as interseções com uma letra do alfabeto usado. Viajando ao longo da curva, a palavra é determinada registrando cada letra à medida que uma interseção é passada. Gauss notou que a distância entre o momento em que o mesmo símbolo aparece em uma palavra é um número inteiro par .

Teoria do grupo

Walther Franz Anton von Dyck começou o trabalho de combinatória em palavras na teoria dos grupos por meio de seu trabalho publicado em 1882 e 1883. Ele começou usando palavras como elementos de grupo. Lagrange também contribuiu em 1771 com seu trabalho sobre grupos de permutação .

Um aspecto da combinatória de palavras estudadas na teoria dos grupos são as palavras reduzidas. Um grupo é construído com palavras em algum alfabeto, incluindo geradores e elementos inversos , excluindo fatores que aparecem na forma aā ou āa, para alguns a no alfabeto. Palavras reduzidas são formadas quando os fatores aā, āa são usados para cancelar elementos até que uma palavra única seja alcançada.

As transformações Nielsen também foram desenvolvidas. Para um conjunto de elementos de um grupo livre , uma transformação Nielsen é alcançada por três transformações; substituindo um elemento por seu inverso, substituindo um elemento pelo produto dele mesmo e de outro elemento, e eliminando qualquer elemento igual a 1. Ao aplicar essas transformações, conjuntos reduzidos de Nielsen são formados. Um conjunto reduzido significa que nenhum elemento pode ser multiplicado por outros elementos para cancelar completamente. Também há conexões com as transformações de Nielsen com palavras sturmianas.

Problemas considerados

Um problema considerado no estudo da combinatória de palavras na teoria dos grupos é o seguinte: para dois elementos x, y de um semigrupo , faz x = y módulo as relações definidoras de x e y. Post e Markov estudaram esse problema e determinaram que é indecidível . Indecidível significa que a teoria não pode ser provada.

A questão de Burnside foi provada usando a existência de uma palavra infinita sem cubos . Esta questão pergunta se um grupo é finito se o grupo tem um número definido de geradores e atende aos critérios x ⁿ = 1, para x no grupo.

Muitos problemas de palavras são indecidíveis com base no problema de correspondência do Post . Quaisquer dois homomorfismos com um domínio comum e um codomínio comum formam uma instância do problema de correspondência Post, que pergunta se existe uma palavra no domínio tal que . Post provou que esse problema é indecidível; conseqüentemente, qualquer problema de palavras que possa ser reduzido a esse problema básico é igualmente indecidível. ${\ displaystyle g, h}$ ${\ displaystyle w}$ ${\ displaystyle g (w) = h (w)}$

Outras aplicações

A combinação de palavras tem aplicações em equações . Makanin provou que é possível encontrar uma solução para um sistema finito de equações, quando as equações são construídas a partir de palavras.

Veja também

Referências

Leitura adicional

As origens da combinatória nas palavras , Jean Berstel, Dominique Perrin , European Journal of Combinatorics 28 (2007) 996-1022
Combinatória de palavras - um tutorial , Jean Berstel e Juhani Karhumäki. Touro. EUR. Assoc. Theor. Comput. Sci. EATCS, 79: 178–228, 2003.
Combinatorics on Words: A New Challenging Topic , Juhani Karhumäki.
Choffrut, Christian; Karhumäki, Juhani (1997). "Combinatória de palavras". Em Rozenberg, Grzegorz; Salomaa, Arto (eds.). Manual de linguagens formais . 1 . Springer. CiteSeerX 10.1.1.54.3135 . ISBN 978-3-540-60420-4 .
Lothaire, M. (1983), Combinatorics on words , Encyclopedia of Mathematics and its Applications, 17 , Addison-Wesley Publishing Co., Reading, Mass., ISBN 978-0-201-13516-9 , MR 0675953 , Zbl 0514.20045 CS1 maint: parâmetro desencorajado ( link )
Lothaire, M. (2002), Algebraic combinatorics on words , Encyclopedia of Mathematics and its Applications, 90 , Cambridge University Press , ISBN 978-0-521-81220-7 , MR 1905123 , Zbl 1001.68093 CS1 maint: parâmetro desencorajado ( link )
"Palavras infinitas: autômatos, semigrupos, lógica e jogos", Dominique Perrin, Jean Éric Pin, Academic Press, 2004, ISBN 978-0-12-532111-2 .
Lothaire, M. (2005), Aplicada combinatória em palavras , Enciclopédia de Matemática e suas Aplicações, 105 , Cambridge University Press , ISBN 978-0-521-84802-2 , MR 2165687 , Zbl 1133.68067 CS1 maint: parâmetro desencorajado ( link )
" Algorithmic Combinatorics on Partial Words ", Francine Blanchet-Sadri, CRC Press, 2008, ISBN 978-1-4200-6092-8 .
Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009), Combinatorics on words. Palavras de Christoffel e repetições em palavras , CRM Monograph Series, 27 , Providence, RI: American Mathematical Society , ISBN 978-0-8218-4480-9 , Zbl 1161.68043
"Combinatorics of Compositions and Words", Silvia Heubach , Toufik Mansour , CRC Press, 2009, ISBN 978-1-4200-7267-9 .
"Equações de palavras e tópicos relacionados: 1º workshop internacional, IWWERT '90, Tübingen, Alemanha, 1 a 3 de outubro de 1990: procedimentos", Editor: Klaus Ulrich Schulz, Springer, 1992, ISBN 978-3-540-55124-9
" Jewels of stringology: text algoritms ", Maxime Crochemore, Wojciech Rytter , World Scientific, 2003, ISBN 978-981-02-4897-0
Berthé, Valérie ; Rigo, Michel, eds. (2010). Combinatória, autômatos e teoria dos números . Enciclopédia de Matemática e suas Aplicações. 135 . Cambridge: Cambridge University Press . ISBN 978-0-521-51597-9 . Zbl 1197.68006 .
Berstel, Jean; Reutenauer, Christophe (2011). Séries racionais não comutativas com aplicações . Enciclopédia de matemática e suas aplicações. 137 . Cambridge: Cambridge University Press . ISBN 978-0-521-19022-0 . Zbl 1250.68007 .
"Patterns in Permutations and Words", Sergey Kitaev, Springer, 2011, ISBN 9783642173325
"Distribution Modulo One and Diophantine Approximation", Yann Bugeaud, Cambridge University Press, 2012, ISBN 9780521111690

Languages

In other projects