Autómata de Müller

En la teoría de autómatas , un autómata de Muller es un tipo de ω-autómata . La condición de aceptación distingue a un autómata de Muller de otros ω-autómatas. El autómata de Muller se define mediante una condición de aceptación de Muller , es decir, el conjunto de todos los estados visitados infinitas veces debe ser un elemento del conjunto de aceptación. Tanto los autómatas de Muller deterministas como los no deterministas reconocen los lenguajes ω-regulares . Reciben su nombre de David E. Muller , matemático e informático estadounidense , quien los inventó en 1963. ^{[ 1 ]}

Formalmente, un autómata de Muller determinista es una tupla A  =  ( Q ,Σ,δ, q ₀ , F ) que consta de la siguiente información:

• Q es un conjunto finito . Los elementos de Q se denominan estados de A.
• Σ es un conjunto finito llamado alfabeto de A.
• δ: Q × Σ → Q es una función, llamada función de transición de A.     
• q ₀ es un elemento de Q , llamado estado inicial.
• F es un conjunto de conjuntos de estados. Formalmente, F ⊆ P ( Q ) donde P ( Q ) es el conjunto potencia de Q . F define la condición de aceptación . A acepta exactamente aquellas secuencias en las que el conjunto de estados que ocurren infinitamente a menudo es un elemento de F 

En un autómata de Muller no determinista , la función de transición δ se reemplaza por una relación de transición Δ que devuelve un conjunto de estados, y el estado inicial q₀ se reemplaza por un conjunto de estados iniciales _{Q₀ . Generalmente, "autómata de Muller" se refiere a un autómata} de Muller no determinista.

Para una formalización más completa, consulte el ω-autómata .

Los autómatas de Muller son igualmente expresivos que los autómatas de paridad , los autómatas de Rabin , los autómatas de Streett y los autómatas de Büchi no deterministas , entre otros, y son estrictamente más expresivos que los autómatas de Büchi deterministas. La equivalencia entre los autómatas mencionados y los autómatas de Muller no deterministas se puede demostrar fácilmente, ya que las condiciones de aceptación de estos últimos pueden emularse utilizando la condición de aceptación de los autómatas de Muller, y viceversa.

El teorema de McNaughton demuestra la equivalencia entre el autómata de Büchi no determinista y el autómata de Muller determinista. Por lo tanto, los autómatas de Muller deterministas y no deterministas son equivalentes en cuanto a los lenguajes que pueden aceptar.

A continuación se presenta una lista de construcciones de autómatas que transforman cada una de un tipo de ω-autómata en un autómata de Muller no determinista.

De los autómatas de Büchi

Si B es el conjunto de estados finales en un autómata de Büchi con el conjunto de estados Q , podemos construir un autómata de Muller con el mismo conjunto de estados, función de transición y estado inicial con la condición de aceptación de Muller como F = { X | X ∈ P ( Q ) ∧ X ∩ B ≠ ∅ }.

De los autómatas de Rabin/autómatas de paridad

De manera similar, las condiciones de Rabin${\displaystyle (E_{j},F_{j})}$se puede emular construyendo el conjunto de aceptación en el autómata de Muller como todos los conjuntos${\displaystyle F\subseteq Q}$que satisfacen${\displaystyle F\cap E_{j}=\emptyset }$y${\displaystyle F\cap F_{j}\neq \emptyset }$, para algún j . Nótese que esto también cubre el caso de los autómatas de paridad, ya que la condición de aceptación de paridad se puede expresar fácilmente como una condición de aceptación de Rabin.

Autómatas de Streett

Las condiciones de Streett${\displaystyle (E_{j},F_{j})}$se puede emular construyendo el conjunto de aceptación en el autómata de Muller como todos los conjuntos${\displaystyle F\subseteq Q}$que satisfacen${\displaystyle F\cap F_{j}=\emptyset \implies F\cap E_{j}=\emptyset }$, para todo j .

Autómata de Büchi

El teorema de McNaughton proporciona un procedimiento para transformar cualquier autómata de Büchi no determinista en un autómata de Muller determinista.

• Autómatas en diapositivas de palabras infinitas para un tutorial de Paritosh K. Pandya.
• Yde Venema (2008) Lecciones sobre el μ-cálculo modal ; la versión de 2006 se presentó en la 18.ª Escuela Europea de Verano en Lógica, Lenguaje e Información.