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}$.
翻译：程序覆盖式计算模型源于 Barrington 的证明, 该模型捕捉到复杂的等级 $\ mathsf{NC ⁇ 1} $ 。 在这里, 我们在理解模型的微妙性上取得了进步 。 首先, 我们确定一组单体的一种新的 tamenity 条件, 它包含一种自然特性, 由单体程序识别的常规语言在类中的单体。 其次, 我们证明, 被称为 $\ mathb{DA} $ 的类别满足了 tamenity, 因此, 单体($\ mathbf{DA}) $ 的方案所承认的常规语言正是古典意义上的, 由形态学派从 $\ mathb{DA} $ 中识别的。 第三, 我们通过对比, 我们显示, 被研究透彻的单体类的 $\mathbf{J} $ 不是 tame 。 最后, 我们展示了在单体中被方案承认的基于单体 $\ mathb{D} $ 中基于程序等级的程序的等级 。
相关内容
微信扫码咨询专知VIP会员