Alexandra Silva: Towards a Nominal Chomsky Hierarchy

One of the cornerstones in Theoretical Computer Science is the seminal result of Kleene characterising the languages accepted by deterministic finite automata by regular expressions. Regular languages play an important role in formal language theory as they are the first level of the Chomsky hierarchy.

In recent years, motivated by applications in Computer Science where having access to an infinite alphabet of input actions is important, we witnessed the development of nominal automata theory. The nominal Warsaw group has provided extensive results on the operational side: analogue notions to deterministic finite automata, non-deterministic finite automata, pushdown automata and Turing machines. Surprising differences with classical theory were soon discovered: for instance, non-deterministic nominal automata are strictly more powerful than deterministic nominal automata.

In this talk, we take a denotational approach and we initiate a systematic study towards the development of a nominal Chomsky hierarchy. We will start by characterising the languages accepted by orbit-finite deterministic nominal automata. We provide both a semantic and a syntactic characterisation. On the semantic side, we show that nominal regular languages are the final coalgebra in the category of orbit-finite deterministic automata. On the syntactic side, we make two crucial observations. First, that taking the obvious approach and using Nominal Kleene algebra is not enough. In fact, we show that the languages denoted by expressions of nominal Kleene algebra are strictly smaller than the languages accepted by orbit-finite deterministic automata. Second, we show that replacing the star operator by a suitable fixpoint operator yields the desired nominal version of Kleene's theorem.