Para que são utilizadas as redes?

15

A Wikipedia diz :

Malhas completas aparecem em muitas aplicações em matemática e ciência da computação

Está apenas se referindo ao fato de que a álgebra booleana padrão usada em computação é uma treliça completa? Existe algo que ganhamos trabalhando no nível abstrato de treliças, em vez de especificamente com a lógica booleana?

Uma pesquisa no google não encontra muito sobre o assunto, mas provavelmente estou usando as palavras-chave erradas.

Xodarap
fonte
en.wikipedia.org/wiki/Intuitionistic_logic e outras lógicas não clássicas usam vários tipos de redes completas para sua semântica.
András Salamon

Respostas:

11

Veja, por exemplo, este livro: Lattice Theory with Applications, Vijay K. Garg , que começa da seguinte maneira:

A ordem parcial e a teoria da rede agora desempenham um papel importante em muitas disciplinas da ciência da computação e engenharia. Por exemplo, eles têm aplicativos em computação distribuída (relógios vetoriais, detecção global de predicados), teoria da concorrência (pomsets, redes de ocorrência), semântica da linguagem de programação (semântica de ponto fixo) e mineração de dados (análise de conceito). Eles também são úteis em outras disciplinas da matemática, como combinatória, teoria dos números e teoria dos grupos. Neste livro, apresento resultados importantes na teoria da ordem parcial, juntamente com suas aplicações na ciência da computação. O viés do livro é sobre aspectos computacionais da teoria da rede (algoritmos) e sobre aplicativos (especialmente sistemas distribuídos).

O livro não parece mencionar a teoria da recursão (teoria dos conjuntos computáveis), mas no artigo da Wikipedia sobre teoria da computabilidade , vemos:

Quando Post definiu a noção de um conjunto simples como um redefinição com um complemento infinito que não contém nenhum redefinição infinita, ele começou a estudar a estrutura dos conjuntos recursivamente enumeráveis ​​em inclusão. Essa estrutura tornou-se uma estrutura bem estudada. Conjuntos recursivos podem ser definidos nessa estrutura pelo resultado básico de que um conjunto é recursivo se e somente se o conjunto e seu complemento forem ambos recursivamente enumeráveis. Os conjuntos infinitos de repetições sempre têm subconjuntos recursivos infinitos; por outro lado, conjuntos simples existem, mas não possuem um superconjunto recursivo coinfinito. Post (1944) introduziu conjuntos já hipersimples e hiperhipersimples; conjuntos máximos posteriores foram construídos, que são reconfigurações, de modo que todo reconfigurado seja uma variante finita do conjunto máximo fornecido ou seja co-finito. Postar' A motivação original de s no estudo dessa estrutura foi encontrar uma noção estrutural tal que todo conjunto que satisfaz essa propriedade não esteja no grau de Turing dos conjuntos recursivos nem no grau de Turing do problema de parada. Post não encontrou essa propriedade e a solução para seu problema aplicou métodos de prioridade; Harrington e Soare (1991) encontraram eventualmente essa propriedade.

Para ler mais, consulte a publicação do blog Lattice Theory para programadores e não cientistas da computação .

Pål GD
fonte
2
Deixe-me acrescentar a isso que as redes e a noção relacionada de domínio são muito usadas na semântica das linguagens de programação.
Andrej Bauer
@AndrejBauer você poderia dar algumas dicas para exemplos? Obrigado.
amc
3

As referências dadas por Pål GD são realmente muito apropriadas. Então, vamos nos concentrar em uma questão secundária menor nesta resposta. Já li algumas treliças há algum tempo e comecei a pensar se a noção de semilático não teria sido mais apropriada para aplicações. Você pode objetar que uma semi-rede completa também é automaticamente uma rede, mas os homomorfismos e subestruturas (por exemplo, subátomos e subsemiláticos) são diferentes.

Encontrei (semi-) reticulados pela primeira vez ao estudar semigrupos, como semigrupos comutativos idempotentes. Depois, pensei na relação entre estruturas hierárquicas e treliças e notei que uma árvore é naturalmente também um semilático. Então eu encontrei redes em contextos de segurança e na análise de programas, e sempre me pareceu que a estrutura semilática era a parte realmente importante, e a rede foi usada apenas porque poderia ser obtida "de graça". Mesmo para uma álgebra de Heyting, há uma assimetria entre conjunção e disjunção que sugere para mim que o modelo semilático assimétrico pode fornecer mais informações aqui do que o modelo de rede simétrica.

Thomas Klimpel
fonte
11
Você pode elaborar como as árvores são semiláticas? E especialmente se houver algum teorema interessante, podemos provar sobre estruturas de dados usando (semi-) reticulado?
Xodarap
@Xodarap Se considerarmos uma árvore como um conjunto ordenado parcial, a junção de dois nós é dada pelo menor ancestral comum. Em relação à sua solicitação sobre estruturas de dados, acho que isso está relacionado à minha pergunta anterior sobre estrutura de dados para semiláticos . Minha conclusão na época era que é um problema surpreendentemente não trivial. Além disso, eu tinha pouca intenção de me afastar muito do mainstream, então fiquei muito feliz em encontrar esse post no blog com a grande seção de referência.
Thomas Klimpel
3

um caso muito importante, mas não tão famoso - é bem conhecido entre os teóricos, mas não tão conhecido no sentido de ser ensinado aos estudantes de graduação - do uso de uma treliça é provar limites inferiores superpolinomiais no tamanho de circuitos monótonos Clique em computação pelo qual Razborov ganhou o prêmio Nevanlinna . a construção original é muito técnica, no entanto, e construções posteriores, por exemplo, Berg / Ulfberg, simplificam a estrutura sem a referência a treliças.

portanto, nesse caso, a teoria da rede foi usada como uma estrutura para descobrir a prova original, mas as formulações posteriores tenderam a não se referir a ela diretamente como uma simplificação conceitual.

então sim, as redes podem ser consideradas como um objeto matemático mais exótico [Razborov falou em outro lugar de seu estilo de aplicar matemática avançada ao CS] que pode corresponder a algum outro objeto mais "concreto" no CS; nesse caso, são "portões de aproximação" isto é, portas booleanas em circuitos que dão respostas "aproximadamente corretas" e que a treliça é uma espécie de "estrutura de indução" para converter entre um circuito exato em um circuito aproximado e inexato.

vzn
fonte
2

As etiquetas regulares das arestas e as estruturas relacionadas formam uma rede distributiva (veja, por exemplo, aqui ). Isso pode ser explorado para pesquisar de forma eficiente no espaço de todas as etiquetas de borda regulares para um determinado gráfico (veja aqui ). Como aplicativo, você pode determinar se um mapa pode ser desenhado como cartograma com uma determinada atribuição de área para as faces.

A.Schulz
fonte
2

Surpreendentemente (pelo menos para mim) criptografia . Confira, ele permite novos ataques de sistemas de criptografia conhecidos e dá esperanças de criptografia pós-computação quântica.

Helios
fonte
2
Esse tipo de rede "periódica" não é a mesma que o OP está perguntando. A questão é sobre estruturas com operações binárias que se encontram e se unem.
András Salamon
Opa Então não entendi o que o OP estava perguntando.
Helios
Mas as redes que Helios está falando são de fato redes distributivas na ordem de dominância usual. Além disso, posso estar errado, mas acho que qualquer rede distributiva pode ser incorporada no espaço como um subconjunto de uma rede periódica. E eles são sem dúvida a coisa mais emocionante da criptografia no momento.
Sasho Nikolov 01/07/2013