Sesión Lógica y Computabilidad (II)

Diciembre 15, 11:20 ~ 11:40

Distancia ordinal entre nociones de bisimulación probabilista

Moroni, Martín Santiago

Hay diferentes nociones de bisimulación disponibles para procesos de decisión de Markov sobre espacios de estados continuos, el problema de la caracterización lógica de la bisimilitud en una clase de procesos consiste en probar que la bisimilitud (relacional) es lo mismo que la equivalencia lógica para cada proceso en la clase. Esto es cierto para la clase de los LMP con espacio de estados analítico, pero Sánchez Terraf [Information and Computation, 209(7):p1048] prueba que ambas nociones son en realidad diferentes en la clase de LMP sobre espacios medibles generales. Cabe preguntarse qué ``distancia'' hay entre la bisimulación de estados y la equivalencia lógica para un LMP general $M=(S,\Sigma,\{\tau_a\}_{a \in L})$. Esto fue formalizado por Zhou [Electr. Notes Theor. Comput. Sci., 298:p427] expresando la bisimilitud de estados como el mayor punto fijo de la composición de dos operadores naturales entre relaciones de equivalencia en $S$ y sub-$\sigma$-álgebras de $\Sigma$ y midiendo la distancia como un ordinal. El problema abordado es entonces obtener el supremo de las distancias (ordinales) entre la bisimulación de estados y la equivalencia lógica, sobre la categoría de LMP (sobre espacios con $\sigma$-álgebras contablemente generadas).

Autores: Moroni, Martín Santiago / Sánchez Terraf, Pedro.