Categorical Theory of Automata

自动机范畴论

• 批准号: 470467389
• 负责人: Professor Dr. Stefan Milius
• 金额: --
• 依托单位: Informatik 8 - Theoretische Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/470467389?language=en
• 关键词: Categorical; Theory; Automata

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.

基于有限状态的结构是计算机科学、工程和自然科学中的基本工具。有几十种类型的有限状态设备用于不同类型的行为，例如有限或无限词或树的正则语言，加权或随机语言和数据语言。他们的理论有许多相似之处，例如，通过有限代数识别器和一元二阶逻辑以及类似的算法来进行机器独立的表征。然而，每种类型的系统大多是单独研究的。在CATHY，我们将开发一个新的统一理论，涵盖了有限状态设备的整个行为谱。一致性是建立在应用范畴论的概念上的，范畴论是一种强大的数学理论，非常善于将相似性形式化，并将不同的结构系统地联系起来。我们的目标是一个完全成熟的理论的“规律性”的行为的机器独立于他们的类型。特别是，在经典理论中，通过对偶，机器和有限代数结构之间有着深刻的联系。事实上，这是Eilenberg/Reiterman型对应关系的基础，它将正则行为的属性与其代数识别器的属性相关联，并允许通过profinite方程来指定这些属性。此外，拓扑方法也带来了新的见解和对正则语言理论中现象的更深入的理解。他们通过观察进入这个阶段，即语言的可识别性可以等效地由相应谓词的连续性来描述。一个通用框架的开始，例如一个一般的艾伦伯格/赖特曼型对应关系现在已经到位。然而，拓扑方法，甚至是一个通用的概念的机器仍然missing.In CATHY，我们将通过开发拓扑方法和扩展的对偶在一个通用的框架内，推进在代数语言理论的对偶为基础的方法的艺术状态。我们还将介绍一个概念的通用机器可识别的行为。一个重点将是他们的算法，特别是学习算法的基础上最近的进展coalgebraic自动机学习。 为了证明通用方法的鲁棒性，我们投入了大量的努力来开发新的通用框架的非平凡的应用程序。这包括更驯服的实例，如文本语言，但也有挑战性的，如数据语言，随机语言和量子有限自动机接受的正则语言。总之，我们将通过提供适用于各种类型有限状态行为的通用数学基础，构造和算法的全面机构，为有限状态设备的统一基础做出重大贡献。