The program-over-monoid model of computation originates with Barrington's proof that it captures the complexity class 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 DA satisfies tameness and hence that the regular languages recognized by programs over monoids in DA are precisely those recognizable in the classical sense by morphisms from QDA. Third, we show by contrast that the well studied class of monoids called J is not tame. Finally, we exhibit a program-length-based hierarchy within the class of languages recognized by programs over monoids from DA.
翻译：程序覆盖的计算模式源于 Barrington 的证据证明它捕捉到复杂等级 CN$1$。 我们在这里在理解模型的微妙性方面取得了进展。 首先, 我们确定一类单体的一种新的温和性条件, 这需要对常规语言进行自然定性, 通过程序识别出来自该类的单体。 其次, 我们证明, 被称为DA 的类别满足了调和, 因此, DA 的单体方案所承认的常规语言正是 QDA 的形态特征在古典意义上可以识别的。 第三, 我们通过对比显示, 研究周熟的单体类 J 并不是 tame 。 最后, 我们展示了一种基于程序覆盖于来自DA 的单体的方案所认可的语言类别中的基于程序的长期等级 。
相关内容
微信扫码咨询专知VIP会员