一句话：提出幺半群类的 Tameness 条件，证明 DA 满足该条件并刻画其程序可识别语言，同时表明 J 不满足并给出长度层级。
本文研究 Barrington 提出的幺半群上程序（program over monoid）计算模型，该模型可刻画 NC^1，但其识别能力仍有许多微妙之处。作者首先定义一类幺半群上的新 Tameness 条件，该条件蕴含由该类幺半群上程序识别的正则语言可获自然刻画。随后证明 DA 类满足 Tameness，因此 DA 中幺半群上程序识别的正则语言恰好是可由 QDA 的态射按经典方式识别的语言。作为对比，作者证明研究较多的 J 类并不 tame。最后，他们在 DA 中幺半群上程序识别的语言类内展示了一个基于程序长度的层级。
The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class $\mathsf{NC^1}$. Here we make progress in understanding the subtleties of the model. First, we identify a new tameness condition on a class of monoids that entails a natural characterization of the regular languages recognizable by programs over monoids from the class. Second, we prove that the class known as $\mathbf{DA}$ satisfies tameness and hence that the regular languages recognized by programs over monoids in $\mathbf{DA}$ are precisely those recognizable in the classical sense by morphisms from $\mathbf{QDA}$. Third, we show by contrast that the well studied class of monoids called $\mathbf{J}$ is not tame. Finally, we exhibit a program-length-based hierarchy within the class of languages recognized by programs over monoids from $\mathbf{DA}$.
@article{paperbot1672,
title = {Tameness and the power of programs over monoids in DA},
author = {Nathan Grosshans and Pierre Mckenzie and Luc Segoufin},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 3},
year = {2022},
doi = {10.46298/lmcs-18(3:14)2022}
}