论文标题
伪造和通用代数的有限模型理论：保存，确定性和复杂性
Finite model theory for pseudovarieties and universal algebra: preservation, definability and complexity
论文作者
论文摘要
我们探讨了有限模型理论与多个普遍代数和半群理论的经典流之间的新相互作用。一个关键结果是一个有限代数的示例，其品种在一阶逻辑上不可有限，但具有一阶可确定的有限成员资格问题。该代数见证了乌斯 - 塔尔斯基定理，SP保护定理和伯克霍夫的HSP预测定理的同时失败，并在有限的水平上提供了负面的解决方案，以提供长期的EilenbergSchützenberger问题的一阶配方。该示例还表明，没有任何有限的伪身份基础的伪造可能在一阶逻辑上是有限的公理。其他结果包括确定有限代数的假副词的一阶确定性以及从任何固定模板约束满意度问题到一阶等效品种成员资格问题的映射的一阶确定性，从而提供了各种$ \ texttt {l} $，$ \ textttttttttttttttt $ \ texttt { $ \ texttt {mod} _p（\ texttt {l}）$，$ \ texttt {p} $和无限的其他许多（取决于复杂性理论假设）。
We explore new interactions between finite model theory and a number of classical streams of universal algebra and semigroup theory. A key result is an example of a finite algebra whose variety is not finitely axiomatisable in first order logic, but which has first order definable finite membership problem. This algebra witnesses the simultaneous failure of the Łos-Tarski Theorem, the SP-preservation theorem and Birkhoff's HSP-preservation theorem at the finite level as well as providing a negative solution to a first order formulation of the long-standing Eilenberg Schützenberger problem. The example also shows that a pseudovariety without any finite pseudo-identity basis may be finitely axiomatisable in first order logic. Other results include the undecidability of deciding first order definability of the pseudovariety of a finite algebra and a mapping from any fixed template constraint satisfaction problem to a first order equivalent variety membership problem, thereby providing examples of variety membership problems complete in each of the classes $\texttt{L}$, $\texttt{NL}$, $\texttt{Mod}_p(\texttt{L})$, $\texttt{P}$, and infinitely many others (depending on complexity-theoretic assumptions).
