论文标题
有限状态自动机的弦图公理化
A String Diagrammatic Axiomatisation of Finite-State Automata
论文作者
论文摘要
我们为有限状态自动机理论开发了一种完全的图形方法，基于将其通常的状态转换图形表示作为字符串图的二维语法。此外，我们提供了一种方程理论，该理论在这种新环境中完全公理化语言等效性。该理论具有两个值得注意的特征。首先，克莱恩之星是一个衍生的概念，因为它可以分解为更原始的代数块。其次，提出的公理化是有限的 - 事实证明，对于正则表达式的一维语法是不可能获得的。
We develop a fully diagrammatic approach to the theory of finite-state automata, based on reinterpreting their usual state-transition graphical representation as a two-dimensional syntax of string diagrams. Moreover, we provide an equational theory that completely axiomatises language equivalence in this new setting. This theory has two notable features. First, the Kleene star is a derived concept, as it can be decomposed into more primitive algebraic blocks. Second, the proposed axiomatisation is finitary -- a result which is provably impossible to obtain for the one-dimensional syntax of regular expressions.
