标题： 非均匀确定性有限自动机在有限代数结构上 显示英文标题

标题： Nonuniform Deterministic Finite Automata over finite algebraic structures

摘要： 非均匀确定性有限自动机（NUDFA）在独异点上由Barrington提出，以研究非均匀常数内存计算的边界。 后来，关于这些自动机的结果有助于识别方程可满足性问题可以在（概率）多项式时间内求解的有趣群类。 基于这些结果，我们给出了具有概率多项式时间算法的恒等式检查问题的群的完整特征。 我们还超越了群的范畴，并提出了如何将NUDFA的概念推广到任意有限代数结构。 我们在这种更一般的设置中研究这些自动机的可满足性。 作为结果，我们给出了从同余模变体中的有限代数的完整描述，对于这些代数，测试电路等价性可以通过概率多项式时间过程来解决。 在我们的证明中，我们使用了两个计算复杂性假设：随机化指数时间假设和常数次数假设。 显示英文摘要

摘要： Nonuniform Deterministic Finite Automata (NUDFA) over monoids were invented by Barrington to study boundaries of nonuniform constant-memory computation. Later, results on these automata helped to indentify interesting classes of groups for which equation satisfiability problem is solvable in (probabilistic) polynomial-time. Based on these results, we present a full characterization of groups, for which the identity checking problem has a probabilistic polynomial-time algorithm. We also go beyond groups, and propose how to generalise the notion of NUDFA to arbitrary finite algebraic structures. We study satisfiability of these automata in this more general setting. As a consequence, we present full description of finite algebras from congruence modular varieties for which testing circuit equivalence can be solved by a probabilistic polynomial-time procedure. In our proofs we use two computational complexity assumptions: randomized Expotential Time Hypothesis and Constant Degree Hypothesis.