Categorical Theory of Automata

有限状态结构是计算机科学、工程和自然科学中的基本工具。存在用于不同类型行为的数十种类型的有限状态装置，例如有限或无限单词或树的规则语言、加权或随机语言以及数据语言。他们的理论有许多相似之处，例如有限代数识别器的机器无关刻画，一种一元二阶逻辑以及类似的算法。然而，每种类型的系统大多是分开研究的。在Cathy中，我们将发展一个新的统一理论，涵盖有限状态器件的所有行为谱。一致性建立在应用范畴理论的概念上，范畴理论是一种强大的数学理论，非常擅长形式化相似之处并系统地将不同的结构联系起来。目标是一种完全成熟的理论，即不受其类型影响的机器行为的“规律性”。特别是，在经典理论中，机器和有限代数结构之间通过对偶性实现了规则行为的深层联系。事实上，这是Eilenberg/Reiterman型对应的基础，它将正则行为的性质与其代数识别器的性质联系起来，并允许用前定方程来说明这些性质。此外，拓扑学方法对正则语言理论中的现象有了新的认识和更深入的理解。他们是通过观察到语言的可识别性可以通过相应谓词的连续性来等价地描述而进入这一阶段的。例如，以一般的艾伦伯格/雷特曼类型的通信为特征的通用框架的开始现在已经到位。然而，拓扑学方法甚至机器的一般概念仍然缺乏。在Cathy中，我们将通过在一般框架内开发拓扑学方法和扩展的对偶性来推进基于对偶的代数语言理论的最新进展。我们还将引入可识别行为的通用机器的概念。重点将放在他们的算法上，特别是基于协代数自动机学习的最新进展的学习算法。为了证明通用方法的健壮性，我们花了大量的努力来开发通用框架的新的重要应用程序。这包括更温和的实例，如文本语言，但也包括具有挑战性的实例，如数据语言、随机语言和量子有限自动机接受的正则语言。综上所述，我们将通过提供适用于广泛类型的有限状态行为的通用数学基础、结构和算法的全面主体，为有限状态设备的统一基础做出实质性贡献。

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.