Sistema de transición

Máquina de estados que puede tener infinitos estados.

En informática teórica , un sistema de transición es un concepto utilizado en el estudio de la computación . Se utiliza para describir el comportamiento potencial de sistemas discretos . Consta de estados y transiciones entre estados, que pueden etiquetarse con etiquetas elegidas de un conjunto; La misma etiqueta puede aparecer en más de una transición. Si el conjunto de etiquetas es un singleton , el sistema esencialmente no está etiquetado 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 abstracta (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 contable.
• El conjunto de transiciones no es necesariamente finito, ni siquiera contable.
• No se proporcionan estados "iniciales" ni estados "finales".

Los sistemas de transición se pueden representar como gráficos dirigidos.

Definicion formal

Formalmente, un sistema de transición es un par donde hay un conjunto de estados y , la relación de transición , es un subconjunto de . Decimos que hay una transición de un estado a otro si y así , y lo denotamos . ${\displaystyle (S,T)}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S\times S}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle (p,q)\in T}$ ${\displaystyle p\rightarrow q}$

Un sistema de transición etiquetado es una tupla donde es un conjunto de estados, es un conjunto de etiquetas y , la relación de transición etiquetada , es un subconjunto de . Decimos que hay una transición de un estado a otro con la etiqueta iff y lo denotamos. ${\displaystyle (S,\Lambda ,T)}$ ${\displaystyle S}$ ${\displaystyle \Lambda }$ ${\displaystyle T}$ ${\displaystyle S\times \Lambda \times S}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle \alpha }$ ${\displaystyle (p,\alpha ,q)\in T}$

${\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 la representación de entradas esperadas, condiciones que deben ser verdaderas para desencadenar la transición o acciones realizadas durante la transición. Los sistemas de transiciones etiquetadas se introdujeron originalmente como sistemas de transición con nombre . ^[1]

Casos especiales

• Si, para cualquier dado y , existe sólo una tupla en , entonces se dice que es determinista (para ). ${\displaystyle p}$ ${\displaystyle \alpha }$ ${\displaystyle (p,\alpha ,q)}$ ${\displaystyle T}$ ${\displaystyle \alpha }$ ${\displaystyle p}$
• Si, para cualquier and dado , existe al menos una tupla en , entonces se dice que es ejecutable (para ). ${\displaystyle p}$ ${\displaystyle \alpha }$ ${\displaystyle (p,\alpha ,q)}$ ${\displaystyle T}$ ${\displaystyle \alpha }$ ${\displaystyle p}$

Formulación de coalgebra

La definición formal se puede reformular de la siguiente manera. Los sistemas de transición de estado etiquetados con etiquetas de corresponden uno a uno con funciones , donde está el funtor de conjunto de potencias (covariante) . Bajo esta biyección se envía a , definida por ${\displaystyle S}$ ${\displaystyle \Lambda }$ ${\displaystyle S\to {\mathcal {P}}(\Lambda \times S)}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle (S,\Lambda ,T)}$ ${\displaystyle \xi _{T}:S\to {\mathcal {P}}(\Lambda \times S)}$

${\displaystyle p\mapsto \{\,(\alpha ,q)\in \Lambda \times S\mid p\xrightarrow {\alpha } q\,\}}$.

En otras palabras, un sistema de transición de estados etiquetado es una coalgebra para el funtor . ${\displaystyle P(\Lambda \times {-})}$

Relación entre el sistema de transición etiquetado y no etiquetado

Hay muchas relaciones entre estos conceptos. Algunas son simples, 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 no etiquetado. Sin embargo, no todas estas relaciones son igualmente triviales.

Comparación con sistemas de reescritura abstracta.

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

Extensiones

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 estructura de Kripke . ^[3]

Los lenguajes de acción son extensiones de los sistemas de transición, que agregan un conjunto de fluidos F , un conjunto de valores V y una función que asigna F × S a V. ^[4]

Ver también

• relación binaria
• relación ternaria
• monoide de transición
• monoide de transformación
• Acción de semigrupo
• Reserva de simulación
• bisimulación
• Semántica operativa
• estructura kripke
• Máquina de estados finitos
• Cálculo μ modal

Referencias

1. Robert M. Keller (julio de 1976) "Verificación formal de programas paralelos", Comunicaciones de la ACM , vol. 19 , núm. 7 , págs. 371–384.
2. Marc Bezem, JW Klop, Roel de Vrijer ("Terese"), Sistemas de reescritura de términos , Cambridge University Press, 2003, ISBN  0-521-39115-6 . págs. 7–8.
3. Christel Baier ; Joost-Pieter Katoen (2008). Principios de verificación de modelos . La prensa del MIT. pag. 20.ISBN​ 978-0-262-02649-9.
4. Micheal Gelfond, Vladimir Lifschitz (1998) "Lenguajes de acción", Artículos electrónicos de Linköping en informática y ciencias de la información , vol. 3 , núm. dieciséis .