一句话:用对合半群及其局部 Hermitian 积刻画有限字上带 neighbour 关系的一阶逻辑,并建立 Eilenberg 型对应。
本文研究有限字上带 neighbour 关系的一阶逻辑 FO(neighbour) 的可定义语言类。为处理字母表上的对合,作者采用对合半群作为识别代数,并定义一种新的半直积——局部 Hermitian 积。主要结果给出代数刻画:一个语言可由 FO(neighbour) 定义,当且仅当它可由一个非周期交换对合半群与一个局部平凡对合半群的局部 Hermitian 积识别。进一步,作者定义语言的对合簇,即在布尔运算、商、对合以及对合态射原像下封闭的语言类,并证明其与对合半群伪簇之间的 Eilenberg 型对应。
We give an algebraic characterisation of first-order logic with the neighbour relation, on finite words. For this, we consider languages of finite words over alphabets with an involution on them. The natural algebras for such languages are involution semigroups. To characterise the logic, we define a special kind of semidirect product of involution semigroups, called the locally hermitian product. The characterisation theorem for FO with neighbour states that a language is definable in the logic if and only if it is recognised by a locally hermitian product of an aperiodic commutative involution semigroup, and a locally trivial involution semigroup. We then define the notion of involution varieties of languages, namely classes of languages closed under Boolean operations, quotients, involution, and inverse images of involutory morphisms. An Eilenberg-type correspondence is established between involution varieties of languages and pseudovarieties of involution semigroups.