Autómata de señales

Formalmente, un autómata de señales es una tupla.${\displaystyle {\mathcal {A}}=\langle \Sigma ,L,L_{0},C,F,\alpha ,\beta ,E\rangle }$que consta de los siguientes componentes:

• ${\displaystyle \Sigma }$es un conjunto finito llamado alfabeto o acciones de${\displaystyle {\mathcal {A}}}$.
• ${\displaystyle L}$es un conjunto finito . Los elementos de${\displaystyle L}$se denominan ubicaciones o estados de${\displaystyle {\mathcal {A}}}$.
• ${\displaystyle C}$es un conjunto finito llamado los relojes de${\displaystyle {\mathcal {A}}}$.
• ${\displaystyle L_{0}\subseteq L}$ es el conjunto de ubicaciones de inicio.
• ${\displaystyle F\subseteq L}$es el conjunto de ubicaciones de aceptación.
• ${\displaystyle \alpha :L\to \Sigma }$que asocia una letra a cada ubicación.
• ${\displaystyle \beta :L\to {\mathcal {B}}(C)}$que asocian restricciones de reloj a cada ubicación, y
• ${\displaystyle E\subseteq L\times {\mathcal {P}}(C)\times L}$es un conjunto de aristas, llamadas transiciones de${\displaystyle {\mathcal {A}}}$, dónde
  • ${\displaystyle {\mathcal {P}}(C)}$es el conjunto potencia de${\displaystyle C}$.

Una ventaja${\displaystyle (\ell ,r,\ell ')}$de${\displaystyle E}$es una transición desde ubicaciones${\displaystyle \ell }$a${\displaystyle \ell '}$que reinician los relojes de${\displaystyle r}$.

Un par con una ubicación${\displaystyle \ell }$y una valoración del reloj${\displaystyle \nu }$se denomina estado extendido o estado .

Nótese que la palabra estado es, por lo tanto, ambigua, ya que, dependiendo del autor, puede significar tanto un par como un elemento de${\displaystyle L}$. Para mayor claridad, este artículo utilizará el término ubicación para referirse al elemento de${\displaystyle L}$y el término ubicación extendida para pares.

Aquí radica una de las mayores diferencias entre los autómatas de señales y los autómatas finitos . En un autómata finito, en algún punto de la ejecución, el estado se describe completamente por el número de letras leídas y por un número finito de valores posibles, que en realidad se denominan "estados". Esto significa que, dado un estado y el sufijo de la palabra a leer, el resto de la ejecución está totalmente determinado. De ahí el término "finito" en el nombre "autómata finito". Sin embargo, como se explica en la sección "ejecución" más adelante, para reanudar la ejecución se utilizan relojes para determinar qué transiciones se pueden realizar. Por lo tanto, para conocer el estado del autómata, es necesario saber tanto en qué posición se encuentra como el valor del reloj.

En el caso de los autómatas finitos, una ejecución consiste esencialmente en una secuencia de ubicaciones, de modo que existe una transición entre dos de ellas. Sin embargo, cabe destacar dos diferencias. La letra no está determinada por la transición, sino por las ubicaciones; esto se debe a que las letras se emiten de forma continua, mientras que las transiciones se realizan de forma discreta. En cada ubicación transcurre cierto tiempo; las restricciones de reloj que identifican una ubicación o su sucesora pueden limitar el tiempo que se permanece en ella.

Una carrera es una secuencia de la forma${\displaystyle {\xrightarrow[{\nu _{0}}]{C}}(\ell _{0},I_{0}){\xrightarrow[{\nu _{1}}]{r_{1}}}(\ell _{1},I_{1})\dots }$que satisfacen ciertas restricciones. Antes de enunciar esas restricciones, se introducen algunas notaciones. Las secuencias son discretas pero representan eventos continuos. Una versión continua de las secuencias${\displaystyle (\sigma _{i})}$,${\displaystyle (\nu _{i})}$,${\displaystyle (\ell _{i})}$Ahora se presentan. Dejemos${\displaystyle i\geq 0}$integral y${\displaystyle t\in I_{i}}$, entonces

• dejar${\displaystyle \sigma '_{t}}$ser igual a${\displaystyle \sigma _{i}}$,
• dejar${\displaystyle \nu '_{t}}$ser${\displaystyle \nu _{i}+t-\lceil I_{i}\rceil }$con${\displaystyle \lceil I_{i}\rceil }$siendo el límite inferior del intervalo${\displaystyle I_{i}}$,
• dejar${\displaystyle \ell '_{t}=\ell _{i}}$.

Las restricciones satisfechas por la ejecución son, para cada${\displaystyle i\geq 0}$integral y${\displaystyle t\geq 0}$real:

• ${\displaystyle \ell _{0}\in L_{0}}$,
• ${\displaystyle (\ell _{i},r_{i},\ell _{i+1})\in E}$,
• ${\displaystyle \nu _{i+1}=(\nu _{i}+\mid I_{i}\mid )[r_{i}\rightarrow 0]}$,
• ${\displaystyle \nu '_{t}\models \beta (\ell '_{t})}$.

La señal definida por esta ejecución es la función${\displaystyle \sigma '}$definido anteriormente. Se dice que la carrera definida anteriormente es una carrera para la señal${\displaystyle \sigma '}$.

La noción de aceptar una secuencia se define como en los autómatas finitos para palabras finitas, y como en los autómatas de Büchi para palabras infinitas. Es decir, si${\displaystyle w}$es de longitud finita${\displaystyle n}$, entonces la ejecución es aceptable si${\displaystyle \ell _{n}\in F}$. Si la palabra es infinita, entonces la secuencia solo acepta si existe un número infinito de posiciones.${\displaystyle i}$de tal manera que${\displaystyle \ell _{i}\in F}$.

Una señal${\displaystyle \gamma }$Se dice que es aceptado por un autómata de señales.${\displaystyle {\mathcal {A}}}$si existe una racha de${\displaystyle {\mathcal {A}}}$en${\displaystyle \gamma }$aceptándolo. El conjunto de señales aceptadas por${\displaystyle {\mathcal {A}}}$se denomina el idioma aceptado por${\displaystyle {\mathcal {A}}}$y se denota por${\displaystyle {\mathcal {S(A)}}}$.

Al igual que en el caso de los autómatas finitos y de Büchi, un autómata de señales puede ser determinista o no determinista. Intuitivamente, ser determinista tiene el mismo significado en ambos casos. Significa que el conjunto de ubicaciones de inicio es un conjunto único y que, dado un estado extendido${\displaystyle s}$y una carta${\displaystyle a}$, solo hay un estado extendido posible al que se puede llegar desde${\displaystyle s}$leyendo${\displaystyle a}$Más precisamente, o bien es posible permanecer en el lugar durante más tiempo, o bien existe como máximo un posible lugar sucesor.

Formalmente, esto se puede definir de la siguiente manera:

• ${\displaystyle L_{0}}$es un singleton
• para cada ubicación${\displaystyle \ell \in L}$, para cada transición${\displaystyle (\ell ,r,\ell ')\in E}$Las dos zonas siguientes son disjuntas:
  • la zona definida por la restricción del reloj${\displaystyle \beta (\ell )}$,
  • la zona definida por la restricción del reloj${\displaystyle \beta (\ell ')}$donde las restricciones en los relojes de${\displaystyle r}$se eliminan,
• para cada transición de ubicación${\displaystyle (\ell ,r',\ell ')\in E}$y${\displaystyle (\ell ,r'',\ell '')\in E}$Las dos zonas siguientes son disjuntas:
  • la zona definida por la restricción del reloj${\displaystyle \beta (\ell ')}$donde las restricciones en los relojes de${\displaystyle r'}$se eliminan,
  • la zona definida por la restricción del reloj${\displaystyle \beta (\ell '')}$donde las restricciones en los relojes de${\displaystyle r''}$se eliminan,

Para simplificar la definición de una secuencia, algunos autores requieren que cada intervalo de una secuencia esté cerrado por la derecha y abierto por la izquierda. Esto restringe los autómatas a aceptar solo señales cuya partición subyacente satisface la misma propiedad. Sin embargo, garantiza que en cada momento${\displaystyle t\geq 0}$,${\displaystyle \lim _{t\leftarrow x^{+}}f(x)=f(t)}$para${\displaystyle f}$representando cualquiera de las funciones${\displaystyle \sigma '}$,${\displaystyle \nu '}$o${\displaystyle \ell '}$presentado anteriormente.

Un autómata de señales bipartito es un autómata de señales en el que la ejecución alterna entre intervalos abiertos e intervalos singulares (es decir, intervalos que son singletons). Garantiza que el grafo subyacente al autómata sea un grafo bipartito y, por lo tanto, que el conjunto de ubicaciones se pueda particionar en${\displaystyle \{L^{o},L^{s}\}}$, el conjunto de ubicaciones abiertas y de ubicaciones singulares. Dado que el primer intervalo contiene 0, no puede ser una ubicación abierta, por lo que se deduce que${\displaystyle L_{0}\subseteq L^{s}}$. Para asegurar que cada ubicación singular sea realmente singular, para cada ubicación${\displaystyle \ell }$, debe haber un reloj${\displaystyle x_{\ell }}$que se restablece al entrar${\displaystyle \ell }$y de tal manera que la restricción del reloj de${\displaystyle \ell }$contiene${\displaystyle x=0}$.

Cualquier autómata de señales puede transformarse en un autómata de señales bipartito equivalente. Basta con reemplazar cada ubicación.${\displaystyle \ell }$por un par de ubicaciones${\displaystyle (\ell ^{o},\ell ^{s})}$y presentar un nuevo reloj${\displaystyle x}$, de tal manera que para cada${\displaystyle \ell }$,${\displaystyle x_{\ell ^{s}}=x}$.

Cerca de allí se muestra un autómata bipartito equivalente al autómata de señales de la sección de ejemplos. Los estados rectangulares representan ubicaciones singulares.