Autómata ω

En la teoría de autómatas , una rama de la informática teórica , un ω- autómata (o autómata de flujo ) es una variación de un autómata finito que se ejecuta con cadenas infinitas, en lugar de finitas, como entrada. Dado que los ω-autómatas no se detienen, poseen diversas condiciones de aceptación en lugar de un simple conjunto de estados de aceptación.

Los autómatas ω son útiles para especificar el comportamiento de sistemas que no se espera que terminen, como el hardware, los sistemas operativos y los sistemas de control . Para estos sistemas, se puede especificar una propiedad como «para cada solicitud, finalmente se envía una confirmación», o su negación «hay una solicitud que no va seguida de una confirmación». La primera es una propiedad de palabras infinitas: no se puede afirmar que una secuencia finita satisfaga esta propiedad.

Las clases de autómatas ω incluyen los autómatas de Büchi , Rabin, Streett, paridad y Muller , cada uno determinista o no determinista. Estas clases de autómatas ω se diferencian únicamente en la condición de aceptación . Todos reconocen con precisión los lenguajes ω regulares, excepto los autómatas de Büchi deterministas, que son estrictamente más débiles que los demás. Si bien todos estos tipos de autómatas reconocen el mismo conjunto de lenguajes ω , difieren en la concisión de su representación para un lenguaje ω dado.

Formalmente, un ω-autómata determinista es una tupla${\textstyle A=(Q,\Sigma ,\delta ,q_{0},A_{acc})}$, que consta de los siguientes componentes:

• ${\textstyle Q}$, es un conjunto finito . Los elementos de${\textstyle Q}$se llaman los estados de${\textstyle A}$.
• ${\textstyle \Sigma }$, es un conjunto finito llamado alfabeto de${\textstyle A}$.
• ${\textstyle \delta \colon Q\times \Sigma \rightarrow Q}$es una función, llamada función de transición de${\textstyle A}$.
• ${\textstyle Q_{0}}$es un elemento de${\textstyle Q}$, llamado estado inicial.
• ${\textstyle A_{acc}}$es un conjunto de estados de aceptación de${\textstyle A}$, formalmente un subconjunto de${\textstyle Q^{\omega }}$.

Una entrada para${\textstyle A}$es una cadena infinita sobre el alfabeto${\textstyle \Sigma }$, es decir, es una secuencia infinita${\textstyle \alpha =(a_{1},a_{2},a_{3},\ldots )}$. La carrera de${\textstyle A}$En dicha entrada hay una secuencia infinita${\textstyle \rho =(r_{0},r_{1},r_{2},\ldots )}$de estados, definidos de la siguiente manera:

• ${\textstyle r_{0}=q_{0}}$.
• ${\textstyle r_{1}=\delta (r_{0},a_{1})}$.
• ${\textstyle r_{2}=\delta (r_{1},a_{2})}$.

...

• es decir, por cada${\textstyle i}$:${\textstyle r_{i}=\delta (r_{i-1},a_{i})}$.

El propósito principal de un autómata ω es definir un subconjunto del conjunto de todas las entradas: el conjunto de entradas aceptadas . Mientras que en el caso de un autómata finito ordinario, cada ejecución termina con un estado${\textstyle r_{n}}$y la entrada se acepta si y solo si${\textstyle r_{n}}$es un estado de aceptación, la definición del conjunto de entradas aceptadas es más complicada para los ω-autómatas. Aquí debemos observar toda la ejecución.${\textstyle \rho }$. La entrada se acepta si la ejecución correspondiente está en${\textstyle {\text{Acc}}}$El conjunto de palabras ω de entrada aceptadas se denomina lenguaje ω reconocido por el autómata, que se denota como${\textstyle L(A)}$.

La definición de${\textstyle {\text{Acc}}}$como un subconjunto de${\textstyle Q^{\omega }}$es puramente formal y no es adecuado para la práctica porque normalmente dichos conjuntos son infinitos. La diferencia entre los distintos tipos de autómatas ω (Büchi, Rabin, etc.) radica en cómo codifican ciertos subconjuntos.${\textstyle {\text{Acc}}}$de${\textstyle Q^{\omega }}$como conjuntos finitos y, por lo tanto, en qué subconjuntos pueden codificar.

Formalmente, un ω-autómata no determinista es una tupla${\textstyle A=(Q,\Sigma ,\Delta ,Q_{0},{\text{Acc}})}$que consta de los siguientes componentes:

• ${\textstyle Q}$es un conjunto finito . Los elementos de${\textstyle Q}$se llaman los estados de${\textstyle A}$.
• ${\textstyle \Sigma }$es un conjunto finito llamado alfabeto de${\textstyle A}$.
• ${\textstyle \Delta }$es un subconjunto de${\textstyle Q\times \Sigma \times Q}$y se denomina relación de transición de${\textstyle A}$.
• ${\textstyle Q_{0}}$es un subconjunto de${\textstyle Q}$, denominado el conjunto inicial de estados.
• ${\textstyle {\text{Acc}}}$es la condición de aceptación , un subconjunto de${\textstyle Q^{\omega }}$.

A diferencia de un ω-autómata determinista, que tiene una función de transición.${\textstyle \delta }$, la versión no determinista tiene una relación de transición${\textstyle \Delta }$. Tenga en cuenta que${\textstyle \Delta }$puede considerarse una función${\textstyle Q\times \Sigma \rightarrow {\mathcal {P}}(Q)}$de${\textstyle Q\times \Sigma }$al conjunto de potencia${\textstyle {\mathcal {P}}(Q)}$. Por lo tanto, dado un estado${\textstyle q_{n}}$y un símbolo${\textstyle a_{n}}$, el siguiente estado${\textstyle q_{n+1}}$No está necesariamente determinado de forma única, sino que existe un conjunto de posibles estados siguientes.

Una carrera de${\textstyle A}$en la entrada${\textstyle \alpha =(a_{1},a_{2},a_{3},\ldots )}$es cualquier secuencia infinita${\textstyle \rho =(r_{0},r_{1},r_{2},\ldots )}$de estados que satisfacen las siguientes condiciones:

• ${\textstyle r_{0}}$es un elemento de${\textstyle Q_{0}}$.
• ${\textstyle r_{1}}$es un elemento de${\estilo de texto \Delta (r_ {0},a_ {1})}$.
• ${\textstyle r_{2}}$es un elemento de${\estilo de texto \Delta (r_ {1},a_ {2})}$.

...

• es decir, por cada${\textstyle i}$:${\textstyle r_{i}}$es un elemento de${\textstyle \Delta (r_{i-1},a_{i})}$.

Un autómata ω no determinista puede admitir muchas ejecuciones diferentes para cualquier entrada dada, o ninguna en absoluto. La entrada se acepta si al menos una de las ejecuciones posibles es de aceptación. Que una ejecución sea de aceptación depende únicamente de${\textstyle {\text{Acc}}}$, como en el caso de los ω-autómatas deterministas. Todo ω-autómata determinista puede considerarse un ω-autómata no determinista tomando${\textstyle \Delta }$ser el gráfico de${\textstyle \delta }$Las definiciones de secuencias y aceptación para los autómatas ω deterministas son, por lo tanto, casos especiales de los casos no deterministas.

Las condiciones de aceptación pueden ser conjuntos infinitos de palabras ω. Sin embargo, generalmente se estudian condiciones de aceptación que son finitamente representables. A continuación se presenta una lista de diversas condiciones de aceptación comunes.

Antes de analizar la lista, hagamos la siguiente observación. En el caso de sistemas que se ejecutan infinitamente, a menudo interesa saber si cierto comportamiento se repite infinitamente. Por ejemplo, si una tarjeta de red recibe infinitas solicitudes de ping, puede que no responda a algunas de ellas, pero debería responder a un subconjunto infinito de las solicitudes de ping recibidas. Esto motiva la siguiente definición: Para cualquier ejecución${\textstyle \rho }$, dejar${\textstyle {\text{Inf}}(\rho )}$sea ​​el conjunto de estados que ocurren infinitamente a menudo en${\textstyle \rho }$Esta noción de que ciertos estados se visitan infinitamente a menudo será útil para definir las siguientes condiciones de aceptación.

• Un autómata de Büchi es un ω-autómata.${\textstyle A}$que utiliza la siguiente condición de aceptación, para algún subconjunto${\textstyle F}$de${\textstyle Q}$:

Condición de Büchi

${\textstyle A}$acepta exactamente esas carreras${\textstyle \rho }$para qué${\textstyle {\text{Inf}}(\rho )\cap F\neq \emptyset }$, es decir, existe un estado de aceptación que ocurre infinitamente a menudo en${\textstyle \rho }$.

• AEl autómata Rabin es un autómata ω${\textstyle A}$que utiliza la siguiente condición de aceptación, para algún conjunto${\textstyle \Omega }$de pares${\textstyle (B_{i},G_{i})}$de conjuntos de estados:

condición de Rabin

${\textstyle A}$acepta exactamente esas carreras${\textstyle \rho }$para el cual existe un par${\textstyle (B_{i},G_{i})}$en${\textstyle \Omega }$de tal manera que${\textstyle B_{i}\cap {\text{Inf}}(\rho )=\emptyset }$y${\textstyle G_{i}\cap {\text{Inf}}(\rho )\neq \emptyset }$.

• Un autómata de Streett es un ω-autómata.${\textstyle A}$que utiliza la siguiente condición de aceptación, para algún conjunto${\textstyle \Omega }$de pares${\textstyle (B_{i},G_{i})}$de conjuntos de estados:

Estado de la calle

${\textstyle A}$acepta exactamente esas carreras${\textstyle \rho }$de tal manera que para todos los pares${\textstyle (B_{i},G_{i})}$en${\textstyle \Omega }$,${\textstyle B_{i}\cap {\text{Inf}}(\rho )\neq \emptyset }$o${\textstyle G_{i}\cap {\text{Inf}}(\rho )=\emptyset }$.

• Un autómata de paridad es un autómata${\textstyle A}$cuyo conjunto de estados es${\textstyle Q=\{0,1,2,\ldots ,k\}}$para algún número natural${\textstyle k}$y que tiene la siguiente condición de aceptación:

Condición de paridad

${\textstyle A}$acepta${\textstyle \rho }$si y solo si el número más pequeño en${\textstyle {\text{Inf}}(\rho )}$es par.

• Un autómata de Muller es un ω-autómata.${\textstyle A}$que utiliza la siguiente condición de aceptación, para un subconjunto${\textstyle \mathbf {F} }$de${\textstyle {\mathcal {P}}(Q)}$(el conjunto de potencias de${\textstyle Q}$):

condición de Muller

${\textstyle A}$acepta exactamente esas carreras${\textstyle \rho }$para qué${\textstyle {\text{Inf}}(\rho )\in \mathbf {F} }$.

Todo autómata de Büchi puede considerarse un autómata de Muller. Basta con reemplazar${\textstyle F}$por${\textstyle \mathbf {F} '}$compuesto por todos los subconjuntos de${\textstyle Q}$que contengan al menos un elemento de${\textstyle F}$De igual modo, todo autómata de Rabin, Streett o de paridad también puede considerarse un autómata de Muller.

El siguiente lenguaje ω${\textstyle L}$sobre el alfabeto${\textstyle \Sigma =\{0,1\}}$, que puede ser reconocido por un autómata de Büchi no determinista: ${\textstyle L}$consta de todas las palabras ω en${\estilo de texto \Sigma ^{\omega }}$en el que 1 aparece solo un número finito de veces. Un autómata de Büchi no determinista que reconoce${\textstyle L}$Solo necesita dos estados${\textstyle q_{0}}$(el estado inicial) y${\textstyle q_{1}}$.${\textstyle \Delta }$consta de las ternas${\textstyle (q_{0},0,q_{0})}$,${\textstyle (q_{0},1,q_{0})}$,${\textstyle (q_{0},0,q_{1})}$y${\textstyle (q_{1},0,q_{1})}$. ${\textstyle F=\{q_{1}\}}$Para cualquier aportación${\textstyle \alpha }$en el que 1 ocurre solo un número finito de veces, hay una secuencia que permanece en estado${\textstyle q_{0}}$siempre que haya 1s para leer y vaya al estado${\textstyle q_{1}}$después. Esta ejecución es exitosa. Si hay infinitos 1, entonces solo hay una ejecución posible: la que siempre permanece en el estado${\textstyle q_{0}}$. (Una vez que la máquina se haya ido${\textstyle q_{0}}$y alcanzó${\textstyle q_{1}}$No puede regresar. Si se lee otro 1, no hay estado sucesor.

Obsérvese que el lenguaje anterior no puede ser reconocido por un autómata de Büchi determinista , que es estrictamente menos expresivo que su contraparte no determinista.

Un lenguaje ω sobre un alfabeto finito${\textstyle \Sigma }$es un conjunto de palabras ω sobre${\textstyle \Sigma }$, es decir, es un subconjunto de${\textstyle \Sigma ^{\omega }}$. Un lenguaje ω sobre${\textstyle \Sigma }$Se dice que es reconocido por un autómata ω.${\textstyle A}$(con el mismo alfabeto) si es el conjunto de todas las palabras ω aceptadas por${\textstyle A}$El poder expresivo de una clase de ω-autómatas se mide por la clase de todos los ω-lenguajes que pueden ser reconocidos por algún autómata de esa clase.

Los autómatas no deterministas de Büchi, paridad, Rabin, Streett y Muller, respectivamente, reconocen exactamente la misma clase de ω-lenguajes. ^{[ 1 ]} Estos se conocen como el cierre ω-Kleene de los lenguajes regulares o como los ω-lenguajes regulares . Usando diferentes demostraciones, también se puede mostrar que los autómatas deterministas de paridad, Rabin, Streett y Muller reconocen los ω-lenguajes regulares. De esto se deduce que la clase de ω-lenguajes regulares es cerrada bajo complementación. Sin embargo, el ejemplo anterior muestra que la clase de autómatas deterministas de Büchi es estrictamente más débil.

Dado que los autómatas no deterministas de Muller, Rabin, Streett, paridad y Büchi son igualmente expresivos, pueden traducirse entre sí. Usemos la siguiente abreviatura:${\displaystyle \{N,D\}\times \{M,R,S,P,B\}}$: por ejemplo, NB significa autómata ω de Büchi no determinista, mientras que DP significa autómata ω de paridad determinista. Entonces se cumple lo siguiente.

• Evidentemente, cualquier autómata determinista puede considerarse como uno no determinista.
• ${\displaystyle NB\rightarrow NR/NS/NP}$sin explosión en el espacio de estados.
• ${\displaystyle NR\rightarrow NB}$con una explosión polinómica en el espacio de estados, es decir, el número de estados en el NB resultante es${\displaystyle 2nm+1}$, dónde${\displaystyle n}$es el número de estados en el NB y${\displaystyle m}$es el número de pares de aceptación de Rabin (véase, por ejemplo, ^{[ 2 ]} ).
• ${\displaystyle NS/NM/NP\rightarrow NB}$con un crecimiento exponencial en el espacio de estados.
• ${\displaystyle NB\rightarrow DR/DP}$con explosión exponencial en el espacio de estados. Este resultado de determinización utiliza la construcción de Safra .

En la fuente web citada se puede encontrar una descripción general completa de las traducciones. ^{[ 3 ]}

Los autómatas ω se pueden usar para demostrar la decidibilidad de S1S, la teoría monádica de segundo orden (MSO) de los números naturales bajo el sucesor. Los autómatas de árbol infinito extienden los autómatas ω a árboles infinitos y se pueden usar para demostrar la decidibilidad de S2S , la teoría MSO con dos sucesores, y esto se puede extender a la teoría MSO de grafos con ancho de árbol acotado (dado un límite fijo) .

• Farwer, Berndt (2002), "ω-Automata", en Grädel, Erich; Thomas, Wolfgang; Wilke, Thomas (eds.), Autómatas, lógica y juegos infinitos , Apuntes de conferencias sobre informática , Springer, págs. 3-21 , ISBN  978-3-540-00388-5.
• Perrin, Dominique; Pin, Jean-Éric (2004), Palabras infinitas: Autómatas, semigrupos, lógica y juegos , Elsevier , ISBN 978-0-12-532111-2
• Thomas, Wolfgang (1990), "Autómatas en objetos infinitos", en van Leeuwen, Jan (ed.), Manual de informática teórica, vol. B , MIT Press , pp. 133–191 , ISBN  978-0-262-22039-2
• Bakhadyr Khoussainov; Anil Nerode (6 de diciembre de 2012). Teoría de autómatas y sus aplicaciones . Springer Science & Business Media. ISBN 978-1-4612-0171-7.