Bisimulación de tartamudeo

Relación entre los sistemas de transición

En la informática teórica , una bisimulación de tartamudeo es una relación entre dos sistemas de transición , máquinas abstractas que modelan la computación. Se define de manera coinductiva y generaliza la idea de bisimulaciones . Una bisimulación hace coincidir los estados de una máquina de modo que las transiciones se correspondan; una bisimulación de tartamudeo permite que las transiciones se correspondan con fragmentos de ruta finitos. ^[1]

Definición

En Principles of Model Checking , Baier y Katoen definen una bisimulación de tartamudeo para un sistema de transición único y luego la adaptan a una relación en dos sistemas de transición. Una bisimulación de tartamudeo para es una relación binaria R en S tal que para todo ( s ₁ , s ₂ ) en R : ${\text{TS}}=(S,{\text{Act}},\to ,I,{\text{AP}},L)$

$Estilo de visualización s_{1},s_{2}$ tienen las mismas etiquetas
Si es una transición válida y entonces existe un fragmento de ruta finito ( ) tal que cada par está en R y está en R $s_{1}\to s_{1}'$ $(s_{1}',s_{2})\no \en R$ $s_{2}u_{1}\cdots u_{n}s_{2}'$ $n\geq 0$ $(s_{1},u_{i})$ $(s_{1}',s_{2}')$
Si es una transición válida y no lo es, entonces existe un fragmento de ruta finito ( ) tal que cada par está en R y está en R $s_{2}\to s_{2}'$ $(s_{1},s_{2}')\no \en R$ $s_{1}v_{1}\cdots v_{n}s_{1}'$ $n\geq 0$ $(v_{i},s_{2})$ $(s_{1}',s_{2}')$

Generalizaciones

Se puede utilizar una generalización, la bisimulación de tartamudeo divergente, para simplificar el espacio de estados de un sistema con la desventaja de que las afirmaciones que utilizan el operador de lógica temporal lineal "next" pueden cambiar el valor de verdad. ^[2] Una bisimulación de tartamudeo robusta permite la incertidumbre sobre las transiciones en el sistema. ^[3]

Referencias

^ Principios de verificación de modelos (páginas 536–580), por Christel Baier y Joost-Pieter Katoen , The MIT Press, Cambridge, Massachusetts.
^ "Abstracción de bisimulación de tartamudeo divergente para síntesis de controlador con especificaciones de lógica temporal lineal". Automatica . 130 . 2021. doi :10.1016/j.automatica.2021.109723. hdl : 10289/14366 .
^ "Bisimulación robusta de tartamudeo para abstracción y síntesis de controlador con perturbación". Automatica . 160 . 2024. doi : 10.1016/j.automatica.2023.111394 .

Este artículo de informática es un esbozo . Puedes ayudar a Wikipedia ampliándolo.

[1] Principios de verificación de modelos (páginas 536–580), por Christel Baier y Joost-Pieter Katoen , The MIT Press, Cambridge, Massachusetts.

[2] "Abstracción de bisimulación de tartamudeo divergente para síntesis de controlador con especificaciones de lógica temporal lineal". Automatica . 130 . 2021. doi :10.1016/j.automatica.2021.109723. hdl : 10289/14366 .

[3] "Bisimulación robusta de tartamudeo para abstracción y síntesis de controlador con perturbación". Automatica . 160 . 2024. doi : 10.1016/j.automatica.2023.111394 .