Duality theory is an important topic within automata theory which leads to a tight relationship between automata and modal logics. These dualities are very much in the spirit of the classical Stone type dualities. In a recent paper by Hundt et al. this was explored in the context of probabilistic automata equipped with a notion of observations. The motivation there was to understand how to reason about systems with hidden state. It turned out to be problematic to formalise this properly in categorical terms and the intuitive notion of duality presented there did not seem to correspond well with what was expected. / We study this putative duality coalgebraically. Towards this, we review coalgebras and view automata as coalgebras for a functor. This provides a natural way to consider categories of automata. We give an alternative construction of the final Kripke automaton of Cordy, which allows us to make the connection to duality. We show that the duality construction of Hundt et al. is in fact a finality construction, and demonstrate an analogous correspondence in the probabilistic case. / 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.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.86515 |
| Date | January 2010 |
| Creators | Al Marhubi, Kamal Amran |
| Contributors | Prakash Panangaden (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0687 seconds