Autómata temporizado alterno

En la teoría de los autómatas , un autómata temporizado alterno (ATA) es una mezcla de autómata temporizado y autómata finito alterno . Es decir, es una especie de autómatas que pueden medir el tiempo y en los que existe una transición universal y existencial.

Los ATA son más expresivos que los autómatas cronometrados. Autómata temporizado alterno de un reloj (OCATA)es la restricción de ATA que permite el uso de un solo reloj. Los OCATA permiten expresar lenguajes cronometrados que no se pueden expresar con un autómata cronometrado. ^[1]

Definición

Un autómata temporizado alterno se define como un autómata temporizado, donde las transiciones son más complejas.

Diferencia de un autómata temporizado

Dado un conjunto , sea el conjunto de combinación booleana positiva de elementos de . Es decir, el conjunto que contiene los elementos de , y que contiene y , para .${\displaystyle X}$${\displaystyle {\mathcal {B}}^{+}(X)}$${\displaystyle X}$${\displaystyle X}$${\displaystyle \phi \land \psi }$${\displaystyle \phi \lor \psi }$${\displaystyle \phi ,\psi \in {\mathcal {B}}^{+}(X)}$

Para cada letra y ubicación , sea ​​un conjunto de restricciones de reloj de modo que sus zonas se dividan con el número de relojes. Dada una valoración de reloj , sea ​​la única restricción de reloj de la que se satisfaga .${\displaystyle a}$${\displaystyle \ell }$${\displaystyle {\mathcal {B}}_{a,\ell }}$${\displaystyle \mathbb {R} _{\geq 0}^{|X|}}$${\displaystyle |X|}$${\displaystyle \nu }$${\displaystyle c(a,\ell ,\nu )}$${\displaystyle {\mathcal {B}}_{a,\ell }}$${\displaystyle \nu }$

Un autómata temporizado alterno contiene una función de transición, que se asocia a una tupla de 3 , con , a un elemento de .${\displaystyle (\ell ,a,c)}$${\displaystyle c\in {\mathcal {B}}_{a,\ell }}$${\displaystyle {\mathcal {B}}^{+}(L\times {\mathcal {P}}(C))}$

Por ejemplo, es un elemento de . Intuitivamente, significa que la carrera puede continuar moviéndose a la ubicación y no reiniciando el reloj. O moviéndose a la ubicación y debería tener éxito cuando se reinicia o .${\displaystyle (\ell _{1},\emptyset )\lor ((\ell _{2},\{x\})\land (\ell _{2},\{y\}))}$${\displaystyle {\mathcal {B}}^{+}(L\times {\mathcal {P}}(C))}$${\displaystyle \ell _{1}}$${\displaystyle \ell _{2}}$${\displaystyle x}$${\displaystyle y}$

Definicion formal

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

• Σ es un conjunto finito llamado alfabeto o acciones de .${\displaystyle {\mathcal {A}}}$
• ${\displaystyle L}$es un conjunto finito . Los elementos de se denominan ubicaciones o estados de .${\displaystyle L}$${\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 E\subseteq L\times \Sigma \times {\mathcal {B}}(C)\to {\mathcal {B}}^{+}(L\times {\mathcal {P}}(C))}$es la función de transiciones de . Es una función parcial, definida como se explicó en la sección anterior.${\displaystyle {\mathcal {A}}}$

Cualquier expresión booleana se puede reescribir en una expresión equivalente en forma disyuntiva normal . En la representación de un ATA, cada disyunción está representada por una flecha diferente. Cada conjunción de una disyunción está representada por un conjunto de flechas con la misma cola y múltiples cabezas. La cola está etiquetada por la letra y cada cabeza está etiquetada por el conjunto de relojes que reinicia.

Correr

Ahora definimos una ejecución de un autómata temporizado alternativo sobre una palabra temporizada . Hay dos formas equivalentes de definir una carrera, ya sea como un árbol o como un juego .${\displaystyle w=(\sigma _{1},t_{1}),(\sigma _{2},t_{2}),\dots ,}$

Corre como un árbol

En esta definición de ejecución, una ejecución ya no es una lista de pares, sino un árbol enraizado . Los nodos del árbol con raíces están etiquetados por pares con una ubicación y una valoración de reloj. El árbol se define de la siguiente manera:

• la raíz del árbol es de la forma con ,${\displaystyle (\ell _{0},\nu _{0})}$${\displaystyle \ell _{0}\in L_{0}}$
• Considere un nodo del árbol en profundidad , con etiqueta . Sin pérdida de generalidad, supongamos que está en forma disyuntiva normal , es decir, es de la forma . Entonces el nodo tiene hijos, para algunos . El -ésimo niño está etiquetado por .${\displaystyle n}$${\displaystyle i}$${\displaystyle (\ell ,\nu )}$${\displaystyle E(a_{i+1},\ell ,c(a,\ell ,\nu ))}$${\displaystyle \bigvee _{i=1}^{n}\bigwedge _{j=1}^{m_{i}}(\ell _{i,j},r_{i,j})}$${\displaystyle n}$${\displaystyle m_{i}}$${\displaystyle 1\leq i\leq n}$${\displaystyle j}$${\displaystyle (\ell _{i,j},(\nu +t_{i+1}-t_{i})[r_{i,j}\to 0]}$

La definición de una ejecución de aceptación difiere dependiendo de si la palabra cronometrada es finita o infinita. Si la palabra cronometrada es finita, entonces la ejecución se acepta si la etiqueta de cada hoja contiene una ubicación de aceptación. Si la palabra cronometrada es infinita, entonces se acepta una ejecución si cada rama contiene un número infinito de ubicaciones de aceptación.

Corre como un juego

Una carrera también se puede definir como un juego de dos jugadores . Llamemos a los dos jugadores "jugador" y "oponente". El objetivo del jugador es crear una carrera de aceptación y el objetivo del oponente es crear una carrera de rechazo (no aceptación).${\displaystyle G_{A,w}}$

Cada estado del juego es una tupla compuesta por una ubicación, una valoración del reloj, una posición en la palabra y, potencialmente, un elemento de . Intuitivamente, una tupla significa que la ejecución ha leído letras, está en la ubicación , con el valor del reloj y que la transición será como la describe . La ejecución se define de la siguiente manera:${\displaystyle {\mathcal {B}}^{+}(L\times {\mathcal {P}}(C))}$${\displaystyle (\ell ,\nu ,i,b)}$${\displaystyle i}$${\displaystyle \ell }$${\displaystyle \nu }$${\displaystyle b}$

• El estado inicial es de la forma , para algunos .${\displaystyle (\ell _{0},\nu _{0},0)}$${\displaystyle \ell _{0}\in L_{0}}$
• dado un estado , si la longitud de la palabra es , la ejecución termina. De lo contrario, su estado sucesor es .${\displaystyle (\ell ,\nu ,i)}$${\displaystyle i}$${\displaystyle (\ell ,\nu ,i,c(a_{i+1},\ell ,\nu ))}$
• El sucesor de un estado es el estado ,${\displaystyle (\ell ,\nu ,i,(\ell ',r))}$${\displaystyle (\ell ',\nu +t_{i}-t_{i-1}[r\to 0],i+1)}$
• El sucesor de un estado es elegido por el jugador, es o ,${\displaystyle (\ell ,\nu ,i,\phi \lor \psi )}$${\displaystyle (\ell ,\nu ,i,\phi )}$${\displaystyle (\ell ,\nu ,i,\psi )}$
• El sucesor de un estado es elegido por el oponente, es o .${\displaystyle (\ell ,\nu ,i,\phi \land \psi )}$${\displaystyle (\ell ,\nu ,i,\phi )}$${\displaystyle (\ell ,\nu ,i,\psi )}$

El conjunto de estados sucesivos que comienzan en un estado de la forma y terminan antes del siguiente estado de este tipo se denomina fase .${\displaystyle (\ell ,\nu ,i)}$

La definición de una ejecución de aceptación es la misma que para los autómatas cronometrados .

Subclase de ATA

Autómata temporizado alterno de un reloj

Un autómata temporizado alterno de un reloj (OCATA) es un autómata temporizado alterno que utiliza un solo reloj.

La expresividad de los OCATA y del autómata temporizado son incomparables.

Por ejemplo, un autómata cronometrado no puede reconocer el idioma sobre el alfabeto de modo que nunca haya exactamente una unidad de tiempo entre dos letras. Sin embargo, la OCATA que se muestra cerca${\displaystyle \{a\}}$

OCATA acepta el idioma en el que no aparecen dos letras en 1 unidad de tiempo de intervalo

lo acepta

OCATA acepta el idioma en el que no aparecen dos letras en 1 unidad de tiempo de intervalo

. En este autómata temporizado alterno, se inician dos ramales. Una rama reinicia el reloj y asegura que cada vez en el futuro cuando se emita una letra, el reloj sea ​​distinto de 1. Esto asegura que entre esta letra y las siguientes, el tiempo transcurrido no sea uno. La segunda rama solo espera a que se emitan otras letras y realiza la misma verificación.${\displaystyle x}$${\displaystyle x}$

ATA puramente universal y puramente existencial

Se dice que un ATA es puramente universal (respectivamente, puramente existencial ) si su función de transición no usa disyunción (respectivamente, conjunción).

Los ATA puramente existenciales son tan expresivos como un autómata temporizado no determinista.

Cierre

La clase de idioma aceptada por las ATA y por las OCATA está cerrada bajo complemento. La construcción se explica para el caso de que exista una única ubicación inicial.

Dado que un ATA acepta un lenguaje cronometrado , su lenguaje complementario es aceptado por un autómata que es esencialmente , donde se define como donde la disyunción y las conjunciones se invierten y simula la ejecución desde cada una de las ubicaciones de simultáneamente.${\displaystyle {\mathcal {A}}=\langle \Sigma ,L,\{q_{0}\},C,F,E\rangle }$${\displaystyle L}$${\displaystyle L^{c}}$${\displaystyle A^{c}}$${\displaystyle \langle \Sigma ,L,\{q_{0}\},C,L\setminus F,E'\rangle }$${\displaystyle E'(\ell ,a,c)}$${\displaystyle E(\ell ,a,c))}$${\displaystyle E'(q_{0},a,c)}$${\displaystyle L_{0}}$

De ello se desprende que la clase de lenguaje aceptada por las ATA y por las OCATA es aceptada por los sindicatos y la intersección. La unión de dos lenguajes se construye tomando copias disjuntas de los autómatas aceptando ambos lenguajes. La intersección se puede construir a partir de unión y concatenación.

Complejidad

El problema del vacío, el problema de la universalidad y el problema de la capacidad de retención para OCATA es decidible, pero no es un problema elemental .

Esos tres problemas son indecidibles sobre los ATA.

Referencias

1. Lasota, SƗawomir; Walukiewicz, Igor (2008). "Autómatas temporizados alternos". Transacciones ACM en lógica computacional . 9 (2): 1–26. arXiv : 1208.5909 . doi : 10.1145 / 1342991.1342994 .