Developments in Higher-Dimensional Automata Theory

Higher dimensional automata (HDAs) were introduced by Pratt and van Glabbeek as a general geometric model for non-interleaving concurrency generalizing standard finite automata, but also Petri nets and event structures. In this setup, autoconcurrency is allowed and events may have a duration. Uli Fahrenberg et al have recently introduced languages of HDAs, which consist of subsumption-closed sets of partially ordered multisets with interfaces (ipomsets), and shown a Kleene theorem and a Myhill-Nerode theorem for them. In this work we further develop the language theory of HDAs. We show a Pumping Lemma which allows us to expose a class of non-regular ipomset languages. We show that inclusion of regular languages is decidable (hence is emptiness), and that intersections of regular languages are again regular. On the other hand, no universal finite HDA exists, so complements of regular languages are not regular. We introduce a width-bounded version of complement and show that width-bounded complements of regular languages are again regular. Contributed talk given by Amazigh AMRANE

Authors

• Amazigh Amrane

Keywords

No keywords are indexed for this paper.