Hispanopedia Wiki
Articulo de referencia

Sistema de transición bien estructurado

En informática, específicamente en el campo de la verificación formal , los sistemas de transición bien estructurados (WSTS, por sus siglas en inglés) constituyen una clase gene...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática, específicamente en el campo de la verificación formal , los sistemas de transición bien estructurados (WSTS, por sus siglas en inglés) constituyen una clase general de sistemas de estados infinitos para los cuales muchos problemas de verificación son decidibles , debido a la existencia de un orden entre los estados del sistema que es compatible con sus transiciones. La primera definición de un sistema de transición bien estructurado (WSTS) general fue introducida por Alain Finkel en su artículo de ICALP de 1987 titulado "Una generalización del procedimiento de Karp y Miller a sistemas de transición bien estructurados". Los resultados de decidibilidad de los WSTS pueden aplicarse a redes de Petri , sistemas de canales con pérdidas, entre otros.

Definición formal

Recordemos que un ordenamiento cuasi-bien≤{\displaystyle \leq }en un platóincógnita{\displaystyle X}es un cuasiordenamiento (es decir, un preorden o una relación binaria reflexiva y transitiva ) tal que cualquier secuencia infinita de elementosincógnita0,incógnita1,incógnita2,…{\displaystyle x_{0},x_{1},x_{2},\ldots }, deincógnita{\displaystyle X}contiene un par crecienteincógnitai≤incógnitaj{\displaystyle x_{i}\leq x_{j}}coni<j{\displaystyle i<j}. El conjuntoincógnita{\displaystyle X}Se dice que está bien casi ordenado , o abreviado wqo .

Para nuestros propósitos, un sistema de transición es una estructuraS=⟨S,→,⋯⟩{\displaystyle {\mathcal {S}}=\langle S,\rightarrow,\cdots \rangle }, dóndeS{\displaystyle S}es cualquier conjunto (sus elementos se llaman estados ), y→ ⊆S×S{\displaystyle \rightarrow \subsetequ S\times S}(sus elementos se denominan transiciones ). En general, un sistema de transiciones puede tener una estructura adicional, como estados iniciales, etiquetas en las transiciones, estados de aceptación, etc. (indicados por los puntos), pero no nos interesan aquí.

Un sistema de transición bien estructurado consta de un sistema de transición.⟨S,→,≤⟩{\displaystyle \langle S,\to,\leq \rangle }, de tal manera que

  • ≤ ⊆S×S{\displaystyle \leq \subsetequ S\times S}es un buen cuasi-ordenamiento en el conjunto de estados.
  • ≤{\displaystyle \leq }es compatible con versiones anteriores→{\displaystyle \to }: es decir, para todas las transicioness1→s2{\displaystyle s_{1}\to s_{2}}(con esto nos referimos a(s1,s2)∈ →{\displaystyle (s_{1},s_{2})\in \to }) y para todost1{\displaystyle t_{1}}de tal manera ques1≤t1{\displaystyle s_{1}\leq t_{1}}, existet2{\displaystyle t_{2}}de tal manera quet1→∗t2{\displaystyle t_{1}{\xrightarrow {*}}t_{2}}(eso es,t2{\displaystyle t_{2}}Se puede acceder desdet1{\displaystyle t_{1}}mediante una secuencia de cero o más transiciones) ys2≤t2{\displaystyle s_{2}\leq t_{2}}.
El requisito de compatibilidad ascendente

Sistemas bien estructurados

Un sistema bien estructurado [ 1 ] es un sistema de transición.(S,→){\displaystyle (S,\to )}con el estado establecidoS=Q×D{\displaystyle S=Q\times D}compuesto por un conjunto finito de estados de controlQ{\displaystyle Q}, un conjunto de valores de datosD{\displaystyle D}, provisto de un preorden decidible≤ ⊆D×D{\displaystyle \leq \subsetequ D\times D}que se extiende a los estados por(q,d)≤(q′,d′)⇔q=q′∧d≤d′{\displaystyle (q,d)\leq (q',d')\Leftrightarrow q=q'\wedge d\leq d'}, que está bien estructurado como se definió anteriormente (→{\displaystyle \to }es monótono, es decir compatible hacia arriba, con respecto a≤{\displaystyle \leq }) y además tiene un conjunto computable de mínimos para el conjunto de predecesores de cualquier subconjunto cerrado hacia arriba deS{\displaystyle S}.

Los sistemas bien estructurados adaptan la teoría de los sistemas de transición bien estructurados para modelar ciertas clases de sistemas que se encuentran en la informática y proporcionan la base para los procedimientos de decisión para analizar dichos sistemas, de ahí los requisitos suplementarios: la definición de un WSTS en sí misma no dice nada sobre la computabilidad de las relaciones.≤{\displaystyle \leq },→{\displaystyle \to }.

Usos en la informática

Sistemas bien estructurados

La cobertura se puede determinar para cualquier sistema bien estructurado, al igual que la alcanzabilidad de un estado de control dado, mediante el algoritmo hacia atrás de Abdulla et al. [ 1 ] o para subclases específicas de sistemas bien estructurados (sujetos a monotonicidad estricta, [ 2 ] por ejemplo en el caso de redes de Petri no acotadas) mediante un análisis hacia adelante basado en un gráfico de cobertura de Karp-Miller .

Algoritmo hacia atrás

El algoritmo hacia atrás permite responder a la siguiente pregunta: dado un sistema bien estructurado y un estados{\displaystyle s}¿Existe alguna ruta de transición que conduzca desde un estado inicial dado?s0{\displaystyle s_{0}}a un estados′≥s{\displaystyle s'\geq s}(se dice que tal estado cubres{\displaystyle s})?

Una explicación intuitiva para esta pregunta es: sis{\displaystyle s}Si un estado representa un estado de error, entonces cualquier estado que lo contenga también debe considerarse un estado de error. Si se puede encontrar un cuasiorden adecuado que modele esta "contención" de estados y que además cumpla con el requisito de monotonicidad respecto a la relación de transición, entonces se puede responder a esta pregunta.

En lugar de un estado de error mínimos{\displaystyle s}, normalmente se considera un conjunto cerrado hacia arribaSmi{\displaystyle S_{e}}de estados de error.

El algoritmo se basa en los hechos de que en un orden cuasi-bueno(A,≤){\displaystyle (A,\leq )}, cualquier conjunto cerrado hacia arriba tiene un conjunto finito de mínimos, y cualquier secuenciaS1⊆S2⊆...{\displaystyle S_{1}\subseteq S_{2}\subseteq ...}de subconjuntos cerrados hacia arriba deA{\displaystyle A}converge después de un número finito de pasos (1).

El algoritmo necesita almacenar un conjunto cerrado hacia arriba.Ss{\displaystyle S_{s}}de estados en memoria, lo cual puede hacer porque un conjunto cerrado hacia arriba es representable como un conjunto finito de mínimos. Comienza desde el cierre hacia arriba del conjunto de estados de error.Smi{\displaystyle S_{e}}y calcula en cada iteración el conjunto (por monotonicidad también cerrado hacia arriba) de predecesores inmediatos y lo agrega al conjuntoSs{\displaystyle S_{s}}. Esta iteración termina después de un número finito de pasos, debido a la propiedad (1) de los cuasiórdenes bien definidos. Sis0{\displaystyle s_{0}}está en el conjunto finalmente obtenido, entonces la salida es "sí" (un estado deSmi{\displaystyle S_{e}}se puede alcanzar), de lo contrario es "no" (no es posible alcanzar dicho estado).

Referencias

  1. 1 2 Parosh Aziz Abdulla, Kārlis Čerāns, Bengt Jonsson, Yih-Kuen Tsay: Análisis algorítmico de programas con dominios bien cuasiordenados (2000), Information and Computation, vol. 160, números 1-2, págs. 109-127
  2. ↑ Alain Finkel y Philippe Schnoebelen, ¡ Sistemas de transición bien estructurados en todas partes!, Theoretical Computer Science 256(1–2), páginas 63–92, 2001.