Reducción de orden parcial en model checking probabilista simbólico

Abstract

El problema fundamental de los model checkers es la explosión exponencial del espacio de estados que se produce al agregar nuevas componentes o variables. El problema se exacerba en los model checkers probabilistas dado que no sólo requiere una búsqueda exhaustiva del espacio de estado, sino cálculos numéricos cuya cantidad de variables y (des)igualdades depende directamente de la cantidad de estados y transiciones. En este trabajo presentamos la implementación de la técnica de orden parcial en un model checker probabilista simbólico. La noción de orden parcial elegida para implementar en este trabajo es la más moderna. Ésta permite una mayor reducción ya que no tiene en cuenta ejecuciones probabilistas irreales consideradas en técnicas anteriores. La implementación se realizó sobre PRISM, que es un model checker probabilista moderno y potente, cuya distribución es de carácter libre.