Estructura de datos isomorfismos

20

Descargo de responsabilidad: no soy un teórico de CS.

Viniendo del álgebra abstracta, estoy acostumbrado a lidiar con cosas que son iguales a un isomorfismo, pero tengo problemas para traducir este concepto a estructuras de datos. Primero pensé que los morfismos biyectivos teóricos establecidos serían suficientes, pero me encontré con una pared con bastante rapidez: esas son solo codificaciones y no capturan la esencia computacional de la estructura de datos.

¿Existe una definición más restrictiva (pero más útil)? (O si no, ¿por qué?) ¿Existe una definición canónica de categoría de "estructuras de datos construidas"?

luego
fuente

Respuestas:

16

No existe una categoría canónica de este tipo, por la misma razón no existe una categoría canónica de cómputos. Sin embargo, existen estructuras algebraicas grandes y útiles en las estructuras de datos.

Una de las estructuras más generales de este tipo, que aún es útil, es la teoría de las especies combinatorias. Una especie es un functor , donde B es la categoría de conjuntos finitos y biyecciones entre ellos. Puede pensar en las especies como familias de estructuras indexadas por conjuntos abstractos de ubicaciones. Esto explica la funcionalidad sobre B : tales familias tienen que ser invariables con respecto al cambio de nombre de las etiquetas abstractas. Luego, el cálculo de especies básicamente reproduce métodos de generación de funciones a nivel de functorial, para generar conjuntos de estructuras de datos en lugar de conteos.F:sisisisi

Para ver esta teoría implementada en un lenguaje de programación, puede leer el documento del Simposio Haskell de Brent Yorgey, Especies y functores y tipos, ¡oh! . Creo que Sage también tiene un paquete de especies, aunque, por supuesto, está orientado al álgebra computacional en lugar de a la programación.

Neel Krishnaswami
fuente
14

De hecho, hay una noción diferente al isomorfismo que es más útil en la programación. Se llama "equivalencia conductual" (a veces llamada "equivalencia observacional") y se establece dando una "relación de simulación" entre estructuras de datos en lugar de biyecciones. Los algebraistas entraron y establecieron un área llamada "tipos de datos algebraicos" en Ciencias de la Computación, donde empujaron los isomorfismos y las álgebras iniciales por un tiempo. Finalmente, los informáticos se dieron cuenta de que estaban siendo engañados. Un buen artículo que habla sobre estos temas es "Sobre equivalencia observacional y especificación algebraica" por Sannella y Tarlecki.

Escribí una respuesta a otra pregunta en teoría sobre relaciones lógicas y simulaciones que habla sobre la historia más general de las relaciones de simulación en informática. Le invitamos a leer eso y hacer un seguimiento de las referencias dadas allí. El Capítulo 5 de "Craft of Programming" de Reynolds es particularmente esclarecedor.

Un libro de texto sobre teoría de autómatas algebraicos de Holcombe tiene la siguiente cita interesante (p. 42):

Hay muchos otros resultados relacionados con homomorfismos y cocientes ... Si bien son de interés algebraico independiente, aún no han demostrado ser particularmente útiles en el estudio de autómatas y áreas relacionadas. De hecho, la teoría algebraica de las máquinas difiere de la dirección tomada en otras teorías algebraicas en un aspecto importante ... Sin embargo, el énfasis en la teoría de los autómatas no es [en] qué máquinas "se ven" sino qué "pueden hacer" . Consideraremos que dos máquinas tienen una relación muy estrecha si ambas pueden "hacer lo mismo", sin embargo, ¡pueden no ser alométricamente isomorfas!

Uday Reddy
fuente
Al reflexionar un poco más sobre la cita de Holcombe, me doy cuenta de que básicamente está diciendo que el álgebra tradicional trata de cómo "se ven" las cosas, es decir, su estructura, pero no tienen idea de qué "pueden hacer", es decir, su comportamiento. Esto parece apuntar a una limitación fundamental del álgebra tradicional con respecto a la informática. Lamentablemente, creo que la teoría de la categoría también pertenece al mismo campo. Pero la teoría de la categoría tiene un estado de "vaca sagrada" y hablar de sus limitaciones se considera poco agradable. Con suerte, los informáticos reunirán suficiente coraje para decirlo más alto.
Uday Reddy
Uday, ¿podrías explicar un poco más sobre cómo (la asimetría?) De la teoría de la categoría parece no encajar bien?
Łukasz Lew
@ ŁukaszLew, si la teoría de la categoría fuera una buena opción, podría decir que todas las expresiones de tipo de cálculo lambda con una variable de tipo X son functores. Pero no lo son, por ejemplo, F (X) = (X -> X) no es un functor.
Uday Reddy
7

En lugar de preguntar cómo podemos fortalecer / debilitar la noción de isomorfismo, otra posibilidad es preguntar: ¿Cuál es la noción correcta de equivalencia entre las estructuras computacionales y cuál es la estructura matemática subyacente a esta noción?

Una gran familia de estructuras son las coalgebras. Las estructuras como listas, árboles, autómatas, tanto de la variedad finita como de la infinita, pueden describirse como coalgebras. Entonces podemos estudiar el homomorfismo o el isomorfismo entre coalgebras.

Sin embargo, incluso los homomorfismos entre coalgebras no cuentan toda la historia. Puede resultarle útil buscar simulaciones, bisimulaciones y otras relaciones lógicas. Si prefiere estrictamente un enfoque algebraico (en lugar de uno relacional), las conexiones de Galois son una opción. Aquí hay algunos puntos de partida.

Vijay D
fuente
2

Descargo de responsabilidad: no estoy seguro de haber entendido su pregunta. ¿Desea hablar sobre el isomorfismo entre dos estructuras de datos o entre dos "especificaciones de estructura de datos"? (A veces se denominan tipos de datos abstractos).

Si considera el modelo de sonda celular, creo que surge fácilmente un concepto de isomorfismo. Esto se debe a que el modelo de sonda celular modela el cálculo mediante un árbol de decisión, por lo que el isomorfismo es fácil de definir. El modelo de sonda celular ayudaría, creo, tanto si considera el isomorfismo entre las implementaciones de la estructura de datos como si considera las especificaciones de la estructura de datos.

Para obtener información sobre el modelo de sonda celular, consulte, por ejemplo, la encuesta de Miltersen. ( Complejidad de la sonda celular: una encuesta )

Si dice más sobre por qué necesita definir el isomorfismo entre las estructuras de datos, podría ser posible proporcionar más ayuda. Siéntase libre de enviarme un mensaje.

Elad
fuente