autómata müller

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

Definicion formal

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 llaman 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 potenciado de Q . F define la condición de aceptación . A acepta exactamente aquellas ejecuciones en las que el conjunto de estados que ocurren con infinita frecuencia es un elemento de  F

En un autómata de Muller no determinista , la función de transición δ se reemplaza con 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 ω-autómata .

Equivalencia con otros ω-autómatas

Los autómatas de Muller son igualmente expresivos como los autómatas de paridad , los autómatas de Rabin , los autómatas de Streett y los autómatas de Büchi no deterministas , por mencionar algunos, y estrictamente más expresivos que los autómatas de Büchi deterministas. La equivalencia de los autómatas anteriores y los autómatas de Muller no deterministas se puede demostrar muy fácilmente ya que las condiciones de aceptación de estos autómatas se pueden emular utilizando la condición de aceptación de los autómatas de Muller y viceversa.

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

Transformación a autómatas de Muller no deterministas

A continuación se muestra una lista de construcciones de autómatas, cada una de las cuales transforma un tipo de ω-autómata en un autómata de Muller no determinista.

De los autómatas Büchi

Si es el conjunto de estados finales en un autómata de Büchi con el conjunto de estados , 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 ≠ }. ${\displaystyle B}$ ${\displaystyle Q}$ ${\displaystyle \emptyset }$

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

De manera similar, las condiciones de Rabin se pueden emular construyendo el conjunto de aceptación en el autómata de Muller como todos los conjuntos que satisfacen y , para algunos j . Tenga en cuenta 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. ${\displaystyle (E_{j},F_{j})}$ ${\displaystyle F\subseteq Q}$ ${\displaystyle F\cap E_{j}=\emptyset }$ ${\displaystyle F\cap F_{j}\neq \emptyset }$

De los autómatas Streett

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

Transformación a autómatas deterministas de Muller

Del autómata Büchi

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

Referencias

1. Müller, David E. (1963). "Secuencias infinitas y máquinas finitas". Cuarto Simposio Anual sobre Teoría de Circuitos de Conmutación y Diseño Lógico (SWCT) : 3–16.

• Autómatas en diapositivas de palabras infinitas para un tutorial de Paritosh K. Pandya.
• Yde Venema (2008) Conferencias 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