En matemáticas , específicamente en la teoría de categorías , un-coalgebra es una estructura definida según un functor , con propiedades específicas como se define a continuación. Tanto para álgebras como para coalgebras , [ aclaración necesaria ] un funtor es una forma conveniente y general de organizar una firma . Esto tiene aplicaciones en la informática : ejemplos de coalgebras incluyen estructuras de datos infinitas y perezosas , como arroyos , y también sistemas de transición .
-coalgebras son duales a-álgebras . Así como la clase de todas las álgebras para una determinada firma y teoría de ecuaciones forman una variedad , también lo hace la clase de todas las-coalgebras que satisfacen una teoría de ecuaciones dada forman una covariedad, donde la firma está dada por .
Definición
Dejar
ser un endofunctor en una categoría. Un-coalgebra es un objeto de junto con un morfismo
de , generalmente escrito como .
Un -coalgebra homomorfismo de a otro -coalgebra es un morfismo
en tal que
- .
Por lo tanto, la -coalgebras para un functor F dado constituyen una categoría.
Ejemplos de
Considere el endofunctor que envía un conjunto a su unión disjunta con el conjunto singleton. Una coalgebra de este endofunctor está dada por, dónde son los llamados números naturales, que consisten en los enteros no negativos y también el infinito, y la función es dado por , por y . De echo, es la coalgebra terminal de este endofunctor.
De manera más general, arregle algún conjunto y considere el functor que envía a . Entonces un-coalgebra es una secuencia finita o infinita sobre el alfabeto , donde es el conjunto de estados y es la función de transición de estado. Aplicar la función de transición de estado a un estado puede producir dos resultados posibles: un elemento de junto con el siguiente estado de la secuencia, o el elemento del conjunto singleton como un "estado final" separado que indica que no hay más valores en la secuencia.
En muchas aplicaciones prácticas, la función de transición de estado de tal objeto coalgebraico puede tener la forma , que se factoriza fácilmente en una colección de "selectores", "observadores", "métodos" . Los casos especiales de interés práctico incluyen observadores que producen valores de atributo y métodos mutantes de la formatomando parámetros adicionales y estados de producción. Esta descomposición es dual a la descomposición de la inicial-álgebras en sumas de 'constructores'.
Sea P la construcción del conjunto de potencias en la categoría de conjuntos, considerada como un funtor covariante. Las P -coalgebras están en correspondencia biyectiva con conjuntos con relación binaria. Ahora bien fijar otro conjunto, A . Entonces, las coalgebras para el endofunctor P ( A × (-)) están en correspondencia biyectiva con los sistemas de transición etiquetados , y los homomorfismos entre las coalgebras corresponden a bisimulaciones funcionales entre los sistemas de transición etiquetados.
Aplicaciones
En ciencias de la computación , coalgebra ha surgido como una forma conveniente y adecuadamente general de especificar el comportamiento de sistemas y estructuras de datos que son potencialmente infinitos, por ejemplo, clases en programación orientada a objetos , flujos y sistemas de transición . Mientras que la especificación algebraica se ocupa del comportamiento funcional, típicamente utilizando tipos de datos inductivos generados por constructores, la especificación coalgebraica se ocupa del comportamiento modelado por tipos de procesos coinductivos que son observables por selectores, muy en el espíritu de la teoría de autómatas . Aquí juegan un papel importante las coalgebras finales , que son conjuntos completos de comportamientos posiblemente infinitos, como los arroyos. La lógica natural para expresar las propiedades de tales sistemas es la lógica modal coalgebraica . [ cita requerida ]
Ver también
Referencias
- B. Jacobs y J. Rutten, Un tutorial sobre (Co) Álgebras e (Co) Inducción. Boletín EATCS 62, 1997, p . 222-259 .
- Jan JMM Rutten: coalgebra universal: una teoría de sistemas. Theor. Computación. Sci. 249 (1): 3 - 80 (2000) .
- J. Adámek, Introducción a coalgebra. Teoría y aplicaciones de las categorías 14 (2005), 157-199
- B. Jacobs, Introducción a Coalgebra. Towards Mathematics of States and Observations (borrador del libro)
- Yde Venema: Autómatas y lógicas de punto fijo: una perspectiva coalgebraica. Información y Computación, 204 (2006) 637-678 .