En informática y teoría de autómatas , un autómata Büchi débil es un formalismo que representa un conjunto de palabras infinitas. Un autómata Büchi débil es una modificación del autómata Büchi tal que para todos los pares de estados y pertenecientes al mismo componente fuertemente conectado , está aceptando si y solo si está aceptando.
Un autómata Büchi acepta una palabra si existe una corrida, tal que al menos un estado ocurra infinitamente a menudo en el estado final establecido . Para los autómatas débiles de Büchi, esta condición es equivalente a la existencia de una carrera que finalmente permanece en el conjunto de estados de aceptación.
Los autómatas Büchi débiles son estrictamente menos expresivos que el autómata Büchi y que el autómata Co-Büchi .
Propiedades
Los autómatas deterministas de Weak Büchi se pueden minimizar a tiempo . [1]
Los lenguajes aceptados por los autómatas Weak Büchi están cerrados bajo unión, intersección y complementación.
Los autómatas Weak Büchi no deterministas son más expresivos que los autómatas Weak Büchi. Como ejemplo, el idioma puede ser decidido por un autómata Büchi débil pero no por un autómata Büchi determinista
Referencias
- ^ Löding, Christof (2001). "Minimización eficiente de los ω-autómatas débiles deterministas". Cartas de procesamiento de información . 79 (3): 105–109. doi : 10.1016 / S0020-0190 (00) 00183-6 .
- Boigelot, Bernard (3 de julio de 2005). "Un procedimiento de decisión eficaz para la aritmética lineal sobre los números enteros y reales" (PDF) . Transacciones ACM en lógica computacional . 6 (3): 614–633. doi : 10.1145 / 1071596.1071601 .