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"?
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.
fuente
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.
fuente