Categorical Theory of Automata

• Applicants: Professor Dr. Stefan Milius; Dr. Henning Urbat
• Subject Area: Theoretical Computer Science
• Term: since 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 470467389

Finite state-based structures are fundamental tools in computer science, engineering and in the natural sciences. There exist dozens of types of finite-state devices for different kinds of behavior, e.g. regular languages of finite or infinite words or trees, weighted or stochastic languages, and data languages. Their theories share many similarities, e.g. machine-independent characterizations by finite algebraic recognizers and by a type of monadic second-order logic as well as similar algorithmics. However, each type of system has mostly been studied separately.In CATHY, we will develop a new unifying theory that covers the whole spectrum of behaviors of finite-state devices. Uniformity is founded on applying the concepts of category theory, a powerful mathematical theory that is very good at formalizing similarities and relating different structures systematically. The goal is a fully fledged theory of 'regularity' of the behavior of machines independent of their type. In particular, in the classical theory there is a deep connection between machines and finite algebraic structures for regular behaviors via duality. In fact, this is the basis for Eilenberg/Reiterman-type correspondences relating properties of regular behaviors with properties of their algebraic recognizers and allowing the specification of such properties by profinite equations. In addition, topological methods have led to new insights and a closer understanding of phenomena in the theory of regular languages. They enter the stage through the observation that recognizability of a language can be equivalently described by continuity of the corresponding predicate. Beginnings of a generic framework featuring e.g. a general Eilenberg/Reiterman-type correspondence are now in place. However, topological methods or even a generic notion of machine are still missing.In CATHY, we will advance the state of the art in the duality based approach to algebraic language theory by developing topological methods and extended dualities within a generic framework. We will also introduce a notion of generic machine for recognizable behavior. A focus will be on their algorithmics, in particular on learning algorithms based on recent advances on coalgebraic automata learning. To demonstrate the robustness of the generic approach we devote substantial efforts towards developing new non-trivial applications of the generic framework. This includes more tame instances such as text languages, but also challenging ones such as data languages, stochastic languages, and regular languages accepted by quantum finite automata. Summing up, we will substantially contribute to unified foundations for finite-state devices by providing a comprehensive body of generic mathematical foundations, constructions and algorithms applicable to a wide range of types of finite-state behaviors.

• DFG Programme: Research Grants