Duality and finality for deterministic and probabilistic automata
Kamal Amran Al Marhubi · eScholarship@McGill (McGill) · 2010
La théorie de la dualité est un sujet important dans la théorie des automates qui mène à une étroite relation entre les automates et les logiques modales. Ces dualités sont tout à fait dans l'esprit des dualités classiques de type Stone. Dans un document récent de Hundt et al. cela a été étudié dans le cadre des automates probabilistes équipés d'une notion d'observation. Leur motivation a été de comprendre comment raisonner sur les systèmes avec des états cachés. Il s'est avéré difficile de formaliser cela correctement en utilisant la théorie des catégories, et la notion intuitive de la dualité qui a été présenté ne semblent pas bien correspondre à ce qui était attendu. Nous étudions cette dualité coalgébriquement. à cette fin, nous passons en revue les coalgèbres et nous regardons les automates comme coalgèbres pour un foncteur. Cela fournit un moyen naturel de considérer les catégories d'automates. Nous donnons une construction alternative de l'automate Kripke final de Cordy, qui nous permet de faire la connexion à la dualité. Nous montrons que la construction de la dualité de Hundt et al. est en fait une construction de finalité, et démontrons une correspondance analogue dans la cas probabiliste.