Sistema de transición

En informática teórica , un sistema de transición es una máquina de estados que puede tener un número infinito de estados. Se utiliza para describir el comportamiento potencial de sistemas discretos . Consta de estados y transiciones entre ellos, que pueden estar etiquetados con etiquetas elegidas de un conjunto; una misma etiqueta puede aparecer en más de una transición. Si el conjunto de etiquetas es un conjunto único , el sistema queda esencialmente sin etiquetar, y es posible una definición más simple que omita las etiquetas.

Los sistemas de transición coinciden matemáticamente con los sistemas de reescritura abstractos (como se explica más adelante en este artículo) y los grafos dirigidos . Se diferencian de los autómatas de estados finitos en varios aspectos:

• El conjunto de estados no es necesariamente finito, ni siquiera numerable.
• El conjunto de transiciones no es necesariamente finito, ni siquiera numerable.
• No se especifican estados "inicial" ni "final".

Los sistemas de transición pueden representarse como grafos dirigidos.

Formalmente, un sistema de transición es un par${\displaystyle (S,T)}$dónde${\displaystyle S}$es un conjunto de estados y${\displaystyle T}$, la relación de transición , es un subconjunto de${\displaystyle S\times S}$Decimos que hay una transición de estado${\displaystyle p}$para declarar${\displaystyle q}$si${\displaystyle (p,q)\in T}$y denotarlo${\displaystyle p\rightarrow q}$.

Un sistema de transición etiquetado es una tupla${\displaystyle (S,\Lambda ,T)}$dónde${\displaystyle S}$es un conjunto de estados,${\displaystyle \Lambda }$es un conjunto de etiquetas, y${\displaystyle T}$, la relación de transición etiquetada , es un subconjunto de${\displaystyle S\times \Lambda \times S}$Decimos que hay una transición de estado${\displaystyle p}$para declarar${\displaystyle q}$con etiqueta${\displaystyle \alpha }$si y solo si${\displaystyle (p,\alpha ,q)\in T}$y denotarlo

${\displaystyle p\xrightarrow {\alpha } q\,.}$

Las etiquetas pueden representar diferentes cosas según el idioma de interés. Los usos típicos de las etiquetas incluyen representar la entrada esperada, las condiciones que deben cumplirse para activar la transición o las acciones realizadas durante la transición. Los sistemas de transición etiquetados se introdujeron originalmente como sistemas de transición con nombre . ^{[ 1 ]}

Existen numerosas relaciones entre estos conceptos. Algunas son sencillas, como observar que un sistema de transición etiquetado, donde el conjunto de etiquetas consta de un solo elemento, es equivalente a un sistema de transición sin etiquetar. Sin embargo, no todas estas relaciones son igualmente triviales.

Como objeto matemático, un sistema de transición sin etiquetar es idéntico a un sistema de reescritura abstracto (sin indexar) . Si consideramos la relación de reescritura como un conjunto indexado de relaciones, como hacen algunos autores, entonces un sistema de transición etiquetado es equivalente a un sistema de reescritura abstracto donde los índices son las etiquetas. Sin embargo, el enfoque del estudio y la terminología son diferentes. En un sistema de transición, el interés radica en interpretar las etiquetas como acciones, mientras que en un sistema de reescritura abstracto, el enfoque está en cómo los objetos pueden transformarse (reescribirse) en otros. ^{[ 2 ]}

En la verificación de modelos , a veces se define un sistema de transición para incluir también una función de etiquetado adicional para los estados, lo que da como resultado una noción que abarca la de la estructura de Kripke . ^{[ 3 ]}

Los lenguajes de acción son extensiones de los sistemas de transición, que añaden un conjunto de ^fluentes F , un conjunto de valores V y una función que mapea F × S a V. [ ^{4 ]}

• Relación binaria
• Relación ternaria
• Monoide de transición
• Monoide de transformación
• Acción de semigrupo
• Pedido anticipado de simulación
• Bisimulación
• Semántica operacional
• Estructura de Kripke
• Máquina de estados finitos
• Cálculo μ modal