En la teoría de autómatas , una rama de la informática teórica , un ω -automaton (o autómata de flujo ) es una variación de autómatas finitos que se ejecuta en cadenas infinitas, en lugar de finitas, como entrada. Dado que los ω-autómatas no se detienen, tienen una variedad de condiciones de aceptación en lugar de simplemente un conjunto de estados de aceptación.
Los ω-autómatas son útiles para especificar el comportamiento de los sistemas que no se espera que terminen, como el hardware, los sistemas operativos y los sistemas de control . Para tales sistemas, uno puede querer especificar una propiedad como "para cada solicitud, finalmente sigue un reconocimiento", o su negación "hay una solicitud que no es seguida por un reconocimiento". La primera es una propiedad de las palabras infinitas: no se puede decir de una secuencia finita que satisfaga esta propiedad.
Las clases de ω-autómatas incluyen los autómatas Büchi , los autómatas Rabin, los autómatas Streett, los autómatas de paridad y los autómatas Muller , cada uno de ellos determinista o no determinista. Estas clases de ω-autómatas difieren solo en términos de condición de aceptación . Todos reconocen con precisión los lenguajes ω regulares, excepto el autómata determinista Büchi, que es estrictamente más débil que todos los demás. Aunque todos estos tipos de autómatas reconocen el mismo conjunto de lenguajes ω , no obstante difieren en la concisión de la representación para un lenguaje ω dado.
Ω-autómatas deterministas
Formalmente, un ω-autómata determinista es una tupla A = ( Q , Σ, δ, Q 0 , Acc ) que consta de los siguientes componentes:
- Q es un conjunto finito . Los elementos de Q se llaman los estados de A .
- Σ es un conjunto finito llamado el alfabeto de la A .
- δ: Q × Σ → Q es una función, llamada función de transición de A .
- Q 0 es un elemento de Q , llamado estado inicial.
- Acc es la condición de aceptación , formalmente un subconjunto de Q ω .
Una entrada para A es una cadena infinita sobre el alfabeto Σ, es decir, es una secuencia infinita α = ( a 1 , a 2 , a 3 , ...). La ejecución de A en dicha entrada es una secuencia infinita ρ = ( r 0 , r 1 , r 2 , ...) de estados, definida de la siguiente manera:
- r 0 = q 0 .
- r 1 = δ ( r 0 , a 1 ).
- r 2 = δ ( r 1 , a 2 ).
- ...
- r norte = δ ( r norte -1 , un norte ).
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 r n y la entrada se acepta si y solo si 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 mirar todo el recorrido ρ. La entrada se acepta si la ejecución correspondiente está en Acc . El conjunto de palabras language de entrada aceptadas se denomina lenguaje ω reconocido por el autómata, que se denota como L (A).
La definición de Acc como un subconjunto de Q ω es puramente formal y no es adecuada para la práctica porque normalmente tales conjuntos son infinitos. La diferencia entre varios tipos de ω-autómatas (Büchi, Rabin, etc.) consiste en cómo codifican ciertos subconjuntos Acc de Q ω como conjuntos finitos y, por lo tanto, en qué subconjuntos pueden codificar dichos subconjuntos.
Ω-autómatas no deterministas
Formalmente, un ω-autómata no determinista es una tupla A = ( Q , Σ, Δ, Q 0 , Acc ) que consta de los siguientes componentes:
- Q es un conjunto finito . Los elementos de Q se llaman los estados de A .
- Σ es un conjunto finito llamado el alfabeto de la A .
- Δ es un subconjunto de Q × Σ × Q y se llama la relación de transición de A .
- Q 0 es un subconjunto de Q , llamado conjunto inicial de estados.
- Acc es la condición de aceptación , un subconjunto de Q ω .
A diferencia de un ω-autómata determinista, que tiene una función de transición δ, la versión no determinista tiene una relación de transición Δ. Tenga en cuenta que Δ se puede considerar como una función: Q × Σ → P ( Q ) desde Q × Σ al conjunto de potencia P ( Q ). Por tanto, dado un estado q n y un símbolo a n , el siguiente estado q n +1 no se determina necesariamente de forma única, sino que existe un conjunto de posibles estados siguientes.
Una corrida de A en la entrada α = ( a 1 , a 2 , a 3 , ...) es cualquier secuencia infinita ρ = ( r 0 , r 1 , r 2 , ...) de estados que satisface las siguientes condiciones :
- r 0 es un elemento de Q 0 .
- r 1 es un elemento de Δ ( r 0 , a 1 ).
- r 2 es un elemento de Δ ( r 1 , a 2 ).
- ...
- r n es un elemento de Δ ( r n -1 , a n ).
Un autómata ω no determinista puede admitir muchas ejecuciones diferentes en cualquier entrada dada, o ninguna. La entrada se acepta si se acepta al menos una de las posibles ejecuciones. La aceptación de una ejecución depende solo de Acc , como ocurre con los ω-autómatas deterministas. Cada ω-autómata determinista se puede considerar como un ω-autómata no determinista tomando Δ como la gráfica de δ. Las definiciones de corridas y aceptación de ω-autómatas deterministas son casos especiales de los casos no deterministas.
Condiciones de aceptación
Las condiciones de aceptación pueden ser conjuntos infinitos de palabras. Sin embargo, la gente estudia principalmente las condiciones de aceptación que son finitamente representables. A continuación, se enumeran una variedad de condiciones de aceptación populares.
Antes de discutir la lista, hagamos la siguiente observación. En el caso de sistemas que se ejecutan infinitamente, a menudo uno está interesado en si cierto comportamiento se repite infinitamente a menudo. Por ejemplo, si una tarjeta de red recibe un número infinito de solicitudes de ping, es posible que no responda a algunas de las solicitudes, pero debería responder a un subconjunto infinito de solicitudes de ping recibidas. Esto motiva la siguiente definición: Para cualquier corrida ρ, sea Inf (ρ) el conjunto de estados que ocurren infinitamente a menudo en ρ. 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 Büchi es un ω-autómata A que usa la siguiente condición de aceptación, para algún subconjunto F de Q :
- Condición Büchi
- A acepta exactamente aquellas corridas ρ para las que Inf (ρ) ∩ F no está vacío, es decir, hay un estado de aceptación que ocurre infinitamente a menudo en ρ.
- A El autómata de Rabin es un ω-autómataAque utiliza la siguiente condición de aceptación, para algún conjunto Ω de pares (B i , G i ) de conjuntos de estados:
- Condición de Rabin
- A acepta exactamente aquellas corridas ρ para las que existe un par (B i , G i ) en Ω tal que B i ∩ Inf (ρ) está vacío y G i ∩ Inf (ρ) no está vacío.
- Un autómata de Streett es un ω-autómata A que utiliza la siguiente condición de aceptación, para algún conjunto Ω de pares (B i , G i ) de conjuntos de estados:
- Condición de Streett
- A acepta exactamente esas corridas ρ tales que para todos los pares (B i , G i ) en Ω, B i ∩ Inf (ρ) está vacío o G i ∩ Inf (ρ) no está vacío.
- Un autómata de paridad es un autómata A cuyo conjunto de estados es Q = {0,1,2, ..., k } para algún número natural k , y que tiene la siguiente condición de aceptación:
- Condición de paridad
- A acepta ρ si y solo si el número más pequeño de Inf (ρ) es par.
- Un autómata de Muller es un ω-autómata A que utiliza la siguiente condición de aceptación, para un subconjunto F de P ( Q ) (el conjunto de potencias de Q ):
- Condición de Muller
- A acepta exactamente esas carreras rho para el cual Inf (ρ) es un elemento de F .
Cada autómata Büchi puede considerarse un autómata Muller. Es suficiente para reemplazar F por F 'que consta de todos los subconjuntos de Q que contienen al menos un elemento de F . De manera similar, cada autómata de Rabin, Streett o paridad también puede considerarse un autómata de Muller.
Ejemplo
El siguiente lenguaje ω L sobre el alfabeto Σ = {0,1}, que puede ser reconocido por un autómata Büchi no determinista: L consta de todas las palabras ω en Σ ω en las que 1 aparece solo un número finito de veces. Un autómata de Büchi no determinista que reconoce L solo necesita dos estados q 0 (el estado inicial) y q 1 . Δ consta de los triples ( q 0 , 0, q 0 ), ( q 0 , 1, q 0 ), ( q 0 , 0, q 1 ) y ( q 1 , 0, q 1 ). F = { q 1 }. Para cualquier entrada α en la que 1 ocurre solo un número finito de veces, hay una ejecución que permanece en el estado q 0 mientras haya 1 para leer, y luego pasa al estado q 1 . Esta ejecución es exitosa. Si hay infinitos unos, entonces solo hay una carrera posible: la que siempre permanece en el estado q 0 . (Una vez que la máquina ha dejado q 0 y alcanzado q 1 , no puede regresar. Si se lee otro 1, no hay estado sucesor).
Tenga en cuenta que el lenguaje anterior no puede ser reconocido por un autómata Büchi determinista , que es estrictamente menos expresivo que su contraparte no determinista.
Poder expresivo de los ω-autómatas
Un ω-lenguaje sobre un alfabeto finito Σ es un conjunto de ω-palabras sobre Σ, es decir, es un subconjunto de Σ ω . Un lenguaje más ω Σ se dice que es reconocido por un autómata ω- A (con el mismo alfabeto) si es el conjunto de todos los omega-palabras aceptadas por 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 en la clase.
Los autómatas no deterministas de Büchi, paridad, Rabin, Streett y Muller, respectivamente, reconocen todos 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 pruebas, también se puede demostrar que la paridad determinista, los autómatas de Rabin, Streett y Muller reconocen todos los lenguajes ω regulares. De esto se deduce que la clase de lenguajes regular regulares está cerrada bajo complementación. Sin embargo, el ejemplo anterior muestra que la clase de autómatas Büchi deterministas es estrictamente más débil.
Conversión entre ω-autómatas
Debido a que los autómatas no deterministas de Muller, Rabin, Streett, parity y Büchi son igualmente expresivos, se pueden traducir entre sí. Usemos la siguiente abreviatura: por ejemplo, NB significa-autómata no determinista de Büchi, mientras que DP significa-autómata de paridad determinista. Entonces lo siguiente es válido.
- Claramente, cualquier autómata determinista puede verse como no determinista.
- sin explosiones en el espacio estatal.
- con una explosión polinomial en el espacio de estados, es decir, el número de estados en el NB resultante es, dónde es el número de estados en el NB yes el número de pares de aceptación de Rabin (ver, por ejemplo, [2] ).
- con explosión exponencial en el espacio estatal.
- con explosión exponencial en el espacio estatal. Este resultado de determinación utiliza la construcción de Safra .
Se puede encontrar una descripción general completa de las traducciones en la fuente web referenciada. [3]
Otras lecturas
- Farwer, Berndt (2002), "ω-Automata", en Grädel, Erich; Thomas, Wolfgang; Wilke, Thomas (eds.), Automata, Logics, and Infinite Games , Lecture Notes in Computer Science , Springer, págs. 3–21, ISBN 978-3-540-00388-5.
- Perrin, Dominique; Pin, Jean-Éric (2004), Infinite Words: Automata, Semigroups, Logic and Games , Elsevier , ISBN 978-0-12-532111-2
- Thomas, Wolfgang (1990), "Autómatas sobre objetos infinitos", en van Leeuwen, Jan (ed.), Handbook of Theoretical Computer Science, vol. B , MIT Press , págs. 133–191, ISBN 978-0-262-22039-2
- Bakhadyr Khoussainov; Anil Nerode (6 de diciembre de 2012). Teoría de los autómatas y sus aplicaciones . Springer Science & Business Media. ISBN 978-1-4612-0171-7.
Referencias
- ^ Safra, S. (1988), "Sobre la complejidad de los ω-autómatas", Actas del 29º Simposio anual sobre los fundamentos de la informática (FOCS '88) , Washington, DC, EE. UU .: IEEE Computer Society, págs. 319–327 , doi : 10.1109 / SFCS.1988.21948.
- ^ Esparza, Javier (2017), Teoría de los autómatas: un enfoque algorítmico (PDF)
- ^ Boker, Udi (18 de abril de 2018). "Traducciones Word-Automata" . Página web de Udi Boker . Consultado el 30 de marzo de 2019 .