A conjectura Ehrenfeucht ou agora que está provada (por Michael H. Albert e John Lawrence e independentemente por Victor S. Guba), o teorema da compactação é uma afirmação sobre a combinatória do monóide livre; é um teorema da ciência da computação teórica e um teorema da álgebra .
A declaração é a seguinte:
Adivinhar Ehrenfeucht, compacidade teorema - Qualquer subconjunto S de um monóide finitos gerado livre tem uma sub finito T com a propriedade de que dois morphisms que coincidem em T coincidem em S .
Um conjunto T com a propriedade da declaração é chamado de um conjunto de teste (Inglês conjunto de teste ) para S . A declaração pode, portanto, ser formulada em:
Outra formulação - Qualquer subconjunto de um monóide finamente gerado tem um conjunto de teste finito.
A conjectura de Ehrenfeucht foi formulada por Andrzej Ehrenfeucht na década de 1970. Ela se origina de pesquisas sobre o problema de decidibilidade da equivalência de sistemas DOL , um caso particular de sistemas L introduzidos pelo biólogo Aristid Lindenmayer para formalizar fenômenos de crescimento (aqui D0L é uma abreviatura para "Interação zero determinista Lindenmayer"). O problema é decidir, por duas morphisms h e g em um monoid finamente gerado e uma palavra w , se houver igualdade para todos . Muitos trabalhos precederam a prova da conjectura, sem levar à prova. Uma história foi contada por Karhumäki em 1984.
A conjectura de Ehrenfeucht acima pode ser vista como uma propriedade de compactação de monóides livres. Também podemos formular a conjectura para sistemas de equações . Para isso, consideramos um alfabeto . Algumas palavras sobre são chamadas de equação sobre . Um sistema de equações é simplesmente um conjunto de equações sobre . Uma solução do sistema em um alfabeto é um morfismo de em tal que para todos de . Dois sistemas e são equivalentes se tiverem o mesmo conjunto de soluções. A generalização da conjectura é:
Conjectura de Ehrenfeucht sobre Equações - Qualquer sistema de equações em um monóide livre com um número finito de variáveis é equivalente a um de seus subsistemas finitos.
As duas declarações da conjectura de Ehrenfeucht são de fato equivalentes. A propriedade de compactação se estende a outros monoides que não os monoides livres.
A forma de equação da conjectura foi usada independentemente por Michael H. Albert e John Lawrence e por Victor S. Guba para demonstrar a conjectura. As duas provas da conjectura de Ehrenfeucht tornam-na uma consequência quase direta do teorema da base de Hilbert . Ambas as provas usam o fato de que um monóide finamente gerado pode ser embutido em outra estrutura algébrica, a saber um grupo metabeliano (en) para Albert e Lawrence, e no anel de matrizes de ordem 2 com coeficientes inteiros para Guba.
As demonstrações originais foram comentadas e desenvolvidas, em particular por Dominique Perrin e Arto Salomaa. John R. Stallings também descreve a evidência como um ponto de partida para um desenvolvimento mais geral. Outra prova é dada por Poulsen.
A incorporação de um monóide livre finamente gerado em um alfabeto no monóide de matrizes quadradas de ordem 2 é feito em duas etapas: primeiro, injetamos o monóide no monóide livre gerado por duas letras , associando a cada letra a palavra , então nós representamos as letras e pelas matrizes
eA injetividade vem do fato de que uma matriz
com coeficientes não negativos representa uma palavra se e somente se . Si , a palavra representada termina com a letra si e a letra si .
Um sistema de equações de palavras é transformado em um sistema de equações algébricas, substituindo cada letra pela matriz
onde são incógnitas comutativas e escrevendo as equações do sistema componente por componente. Pelo teorema da base de Hilbert , o sistema é equivalente a um subsistema finito de , portanto também a um subsistema finito de .