Isomorfismos da estrutura de dados

20

Disclaimer: Eu não sou um teórico de CS.

Vindo da álgebra abstrata, estou acostumado a lidar com coisas iguais a um isomorfismo - mas estou tendo problemas para traduzir esse conceito em estruturas de dados. Primeiro pensei que morfismos bijetivos teóricos diretos seriam suficientes, mas me deparei com uma parede rapidamente - essas são apenas codificações e não capturam a essência computacional da estrutura de dados.

Existe uma definição mais restritiva (mas mais útil)? (Ou, se não, por quê?) Existe uma definição canônica de categoria de "estruturas de dados construídas"?

anon
fonte

Respostas:

16

Não existe uma categoria canônica, pela mesma razão que não existe uma categoria canônica de cálculos. No entanto, existem estruturas algébricas grandes e úteis nas estruturas de dados.

Uma das estruturas mais gerais, que ainda é útil, é a teoria das espécies combinatórias. Uma espécie é um functor , onde B é a categoria de conjuntos finitos e bijeções entre eles. Você pode pensar em espécies como sendo famílias de estruturas indexadas por conjuntos abstratos de locais. Isso explica a funcionalidade em relação a B - essas famílias devem ser invariantes no que diz respeito a renomear os rótulos abstratos. Então, o cálculo das espécies basicamente repete a geração de métodos de função no nível funcional, para gerar conjuntos de estruturas de dados em vez de contagens.F:BBBB

Para ver essa teoria implementada em uma linguagem de programação, você pode ler o artigo do Simpósio Haskell de Brent Yorgey, Espécies , functores e tipos, oh meu! . Eu acho que o Sage também tem um pacote de espécies, embora, é claro, seja mais voltado para a álgebra computacional do que para a programação.

Neel Krishnaswami
fonte
14

De fato, existe uma noção diferente do isomorfismo que é mais útil na programação. É chamado de "equivalência comportamental" (às vezes chamada de "equivalência observacional") e é estabelecido fornecendo uma "relação de simulação" entre estruturas de dados em vez de bijeções. Algebraistas entraram e estabeleceram uma área chamada "tipos de dados algébricos" em Ciência da Computação, onde pressionaram isomorfismos e álgebras iniciais por um tempo. Eventualmente, os cientistas da computação perceberam que estavam sendo enganados. Um bom artigo que fala sobre essas questões é "Sobre equivalência observacional e especificação algébrica" de Sannella e Tarlecki.

Escrevi uma resposta para outra pergunta na história sobre relações lógicas e simulações, que fala sobre a história mais geral das relações de simulação na ciência da computação. Você pode ler isso e acompanhar as referências aqui fornecidas. O capítulo 5 do "Ofício da programação" de Reynolds é particularmente esclarecedor.

Um livro de texto sobre a teoria algébrica de autômatos de Holcombe tem a seguinte citação interessante (p. 42):

Existem muitos outros resultados relacionados a homomorfismos e quocientes ... Embora sejam de interesse algébrico independente, ainda não se mostraram particularmente úteis no estudo de autômatos e áreas afins. De fato, a teoria algébrica das máquinas diverge da direção adotada em outras teorias algébricas em um aspecto importante ... Porém, a ênfase na teoria dos autômatos não é [sobre] como as máquinas "se parecem", mas o que "elas podem fazer". . Consideraremos duas máquinas como estando intimamente relacionadas se ambas puderem "fazer a mesma coisa", mas podem não ser algebricamente isomórficas!

Uday Reddy
fonte
Pensando um pouco mais na citação de Holcombe, percebo que ele está basicamente dizendo que a álgebra tradicional lida com o que "as coisas se parecem", isto é, sua estrutura, mas elas não sabem o que "podem fazer", ou seja, seu comportamento. Isso parece apontar para uma limitação fundamental da álgebra tradicional em relação à Ciência da Computação. Infelizmente, acho que a Teoria da Categoria também pertence ao mesmo campo. Mas a Teoria da categoria tem um status de "vaca sagrada" e falar sobre suas limitações é considerado não-legal. Felizmente, os cientistas da computação reunirão coragem suficiente para falar mais alto.
Uday Reddy
Uday, você poderia elaborar um pouco mais sobre como (a assimetria?) Da teoria das categorias parece não ser uma boa opção?
Asukasz Lew 29/04
@ ŁukaszLew, Se a teoria das categorias fosse uma boa opção, você poderia dizer que todas as expressões de tipo de cálculo lambda digitadas com uma variável de tipo X são functores. Mas eles não são, por exemplo, F (X) = (X -> X) não é um functor.
precisa
7

Em vez de perguntar como podemos fortalecer / enfraquecer a noção de isomorfismo, outra possibilidade é perguntar: Qual é a noção correta de equivalência entre estruturas computacionais e qual é a estrutura matemática subjacente a essa noção.

Uma grande família de estruturas são as barras de carvão. Estruturas como listas, árvores, autômatos, tanto da variedade finita quanto da infinita, podem ser descritas como barras de carvão. Podemos então estudar homomorfismo ou isomorfismo entre barras de carvão.

No entanto, mesmo os homomorfismos entre barras de carvão não contam a história toda. Você pode achar útil procurar simulações, bisimulações e outras relações lógicas. Se você preferir estritamente uma abordagem algébrica (em oposição a uma relacional), as conexões Galois são uma opção. Aqui estão alguns pontos de partida.

Vijay D
fonte
2

Isenção de responsabilidade: não sei se entendi sua pergunta. Deseja falar sobre isomorfismo entre duas estruturas de dados ou entre duas "especificações da estrutura de dados"? (Às vezes, eles são chamados tipos de dados abstratos).

Se você considerar o modelo da sonda celular, acho que um conceito de isomorfismo surge facilmente. Isso ocorre porque o modelo da sonda de célula modela a computação por uma árvore de decisão, portanto é fácil definir o isomorfismo. Acho que o modelo da sonda de célula ajudaria tanto se você considerar o isomorfismo entre as implementações da estrutura de dados quanto se considerar as especificações da estrutura de dados.

Para obter informações sobre o modelo da sonda celular, consulte, por exemplo, a pesquisa da Miltersen. ( Complexidade da sonda celular: uma pesquisa )

Se você disser mais sobre por que precisa definir isomorfismo entre estruturas de dados, talvez seja possível fornecer mais ajuda. Sinta-se livre para me enviar uma mensagem.

Elad
fonte