论文标题
具有恶魔改进的半群的有限代表性
Finite Representability of Semigroups with Demonic Refinement
论文作者
论文摘要
二进制关系的构图和恶魔改进$ \ sqsubseteq $由\ begin {align*}（x，y）\ in（r; s）＆\ iff \ in（x，x，x，z）\ in R \ wedge（z） r \ sqsubseteq s＆\ iff（dom（s）\ subseteq dom（r）\ wedge r \ drilctition_ {dom（s）} \ subseteq s） \ end {align*}其中$ dom（s）= \ {x：\已存在y（x，y）\ in s \} $和$ r \ drimate__ {dom（s）} $表示$ r $ to p pairs $（x，y）$ x \ y in dom（s）$。 引入了Demonic微积分，以建模非确定性程序的总正确性，并已应用于程序验证。 我们证明，抽象$（\ sqsubseteq，;）$（\ leq，\ circ）$结构$结构是与Demonic改进订购的一组二进制关系的同构，这些二进制相关均不能通过任何有限的一阶$（\ leq，\ circ）$ formulas $ Formulas（\ leq，circ）$ FORMULAS进行公理化。我们提供了一个相当简单的，无限的递归公理化，以定义$ r（\ sqsubseteq，;）$。我们证明有限代表$（\ leq，\ circ）$结构在有限的基础上具有表示形式。这似乎是二进制关系与组成类别的签名的第一个示例，其中表示类是不可用的公理，但其中有限代表结构属性的有限表示。
Composition and demonic refinement $\sqsubseteq$ of binary relations are defined by \begin{align*} (x, y)\in (R;S)&\iff \exists z((x, z)\in R\wedge (z, y)\in S) R\sqsubseteq S&\iff (dom(S)\subseteq dom(R) \wedge R\restriction_{dom(S)}\subseteq S) \end{align*} where $dom(S)=\{x:\exists y (x, y)\in S\}$ and $R\restriction_{dom(S)}$ denotes the restriction of $R$ to pairs $(x, y)$ where $x\in dom(S)$. Demonic calculus was introduced to model the total correctness of non-deterministic programs and has been applied to program verification. We prove that the class $R(\sqsubseteq, ;)$ of abstract $(\leq, \circ)$ structures isomorphic to a set of binary relations ordered by demonic refinement with composition cannot be axiomatised by any finite set of first-order $(\leq, \circ)$ formulas. We provide a fairly simple, infinite, recursive axiomatisation that defines $R(\sqsubseteq, ;)$. We prove that a finite representable $(\leq, \circ)$ structure has a representation over a finite base. This appears to be the first example of a signature for binary relations with composition where the representation class is non-finitely axiomatisable, but where the finite representations for finite representable structures property holds.
