代数信息系统和代数L-信息系统的表示

可在www.sciencedirect.com在线获取理论计算机科学电子笔记301（2014）117-129www.elsevier.com/locate/entcs信息系统对代数Domain和代数L-Domain的表示1吴明远，李庆国，周向南2湖南大学中国长沙中国摘要信息系统在描述有序结构中起着重要的作用。 本文引入了代数信息系统和代数L-信息系统的概念。它们与Scott（1982）提出的信息系统具有相同的面向逻辑的风格。 但本文中的公理比现有工作中报道的要简短。我们还证明了这两个新的信息系统分别精确地表示代数整环和代数L整环。基于代数信息系统与代数L-信息系统之间的可逼近映射的概念，我们得到了证明了代数信息系统和代数L-信息系统的相应范畴分别等价于代数Domain和代数L-Domain的范畴关键词：代数论域;代数L-论域;信息系统;范畴等价1引言1982年，Scott [13]引入了信息系统和近似映射的概念，作为面向逻辑的方法来处理编程语言的指称语义。后来，Larsen和Winskel [11]证明了信息系统范畴等价于以连续函数为同态的Scott域范畴。这个范畴也等价于以连续函数作为态射的代数代数结构。1993年，Hoofman [8]引入了表示有界完备连续域的信息系统.Vickers [16]通过考虑传递关系和插值关系，建立了连续偏序集的信息系统表示.Vickers的方法更一般，可以用来表示所有连续域，但它不是Scott风格的。2008年，Spreen和Xu [14]首次引入了广义连续信息系统的概念，1本工作得到了国家自然科学基金项目（NO.11071061，11101135）和国家基础研究计划项目（NO.11071061，11101135）的资助。2011CB311808）。2通讯作者：xnzhou81026@163.comhttp://dx.doi.org/10.1016/j.entcs.2014.01.0101571-0661 © 2014 Elsevier B. V.在CC BY-NC-ND许可下开放访问。118M. Wu et al. /Electronic Notes in Theoretical Computer Science 301（2014）117..斯科特风格，准确地捕捉连续dcpos。他们还提出了一般代数信息系统的概念，通过在一般连续信息系统上添加其他规则来捕获代数域。但在他们的通用代数信息系统中，有许多规则。本文将引入一类新的代数信息系统，其中只有四条规则。L-结构域由Coquand [2]和Jung [9]独立引入。Jung [9，10]证明了L-整环构成了连续整环的极大Carnival闭满子范畴。这对于代数的情况也是一样的。Spreen [14]给出了连续信息系统的一个子类，它可以表示L-整环。但信息系统的条件很多，不容易判断。张[18]提出了一种面向逻辑的方法来代数L-域与根岑风格的证明系统，所以它是从斯科特的原始方法不同。更多关于信息系统的文章可以在[20，21，17，5，6，7]中找到在新的代数信息系统的基础上，我们引入了代数L-信息系统.我们构造代数L-信息系统的方法是巧妙的，完全不同于Spreen的方法。我们对代数L-信息系统的定义是简单的。第二节回顾了Domain理论的一些基本概念，并给出了代数信息系统的定义。我们表明，代数信息系统的状态形成一个代数域的集合包含。代数L-信息系统在第3节中介绍。证明了代数L-信息系统与代数L-整环在代数信息系统与代数整环的关系下是相互对应的。在第四节中，我们分别给出了代数信息系统与代数L-信息系统之间的可逼近映射。证明了相应的代数信息系统和代数L-信息系统范畴分别等价于以Scott连续函数为态射的代数Domain和代数L-Domain范畴2领域和信息系统Domain理论是格理论、拓扑理论、范畴理论和计算机科学的交叉学科。定义域理论的主要目的是给出空间的模型，在其上定义可计算函数。在高级指称语义学中，需要更高类型的空间（例如函数空间）和递归定义的空间（例如自反域）。为了创建所需的结构，还需要许多特殊的域构造（或函子）。本文主要介绍代数整环和代数L-整环。对于任何集合A，我们写F±A表示F是A的有限子集。设P是偏序集，称P的非空子集D是有向的，如果对D的任意两个元素a和b，存在c∈D使得a≤c，b≤c.我们使用X=i∈Idi来表示X是有向集的上确界。一个偏序集称为dcpo，如果每个有向子集都有一个最小上界。设x，y∈P，称x逼近y（符号为xy）当且仅当对每个有向集D<$P，y≤D意味着M. Wu et al. /Electronic Notes in Theoretical Computer Science 301（2014）117119是一个有向集，x=（2006年）B）。 如果dcpo有基，则称它为域。在有一个d∈D使得x≤d。称x是紧的，如果xx（我们用K（P）表示P的所有紧元素的集合）。 设x ={a |a ∈ P; ax}对于每个x∈P. 一个子集B。称为P的基，如果对每一个x∈P，B特别地，如果dcpo的所有紧元素形成基，则称dcpo为代数域。一 个域D是指向的，如果它包含一个最小元素。在两个区域P1和P2之间的函数f称为Scott连续的，如果f保持有向集的所有连接，也就是说，对于P1的有向集D，f（.D）=.f（D）.一个点代数整环，其中每个理想↓x都是一个完备格（在它的诱导阶上），称为代数L整环。代数Domain范畴用AlGDOM表示，其中代数Domain是对象，Scott连续函 数 是 态 射 。 代 数 L-domain 范 畴 是 AlGDOM 的 全 子 范 畴 ， 记 为AlGLDOM，其中所有对象都是代数L-domain。关于域理论的更多结果可以在[1，3，4]中找到。本文中的范畴理论可以在[12，19]中找到。在计算机科学中，信息的概念体系介绍作为一种面向逻辑的方法，编程语言的指称语义。 借助于信息系统，Scott[13]从理论上表示了元素的域。信息系统是非常熟悉的数理逻辑，可以构建具体的域。斯科特[13]引入的信息系统2008年，Spreen和Xu [14]引入了广义连续信息系统的概念，它精确地捕获了连续域。在[14]的第5节中，他们通过对连续信息系统的定义增加另一个要求来刻画一般代数信息系统。然而，我们认为这不是最好的结构，因为代数域有其特殊的性质。一般代数信息系统定义如下：定 义 2.1[14] 设 A 是 一 个 集 合 ， Con 是 A 的 非 空 有 限 子 集 的 集 合 ， 并 且 n=Con×A，一般代数信息系统是三元组（A，Con，n），并且以下规则对所有集合x，y∈Con和所有元素a∈A成立。(1) {a}∈Con，(2) x<$a <$x{a}∈Con，(3) xy和xa ya，(4) xy a xa，(5) x<$y <$$>z ∈Con，x< $z <$$>z <$y，(6) x <$F ± A <$<$z ∈ Con，s.t. Fz和xz。在这个信息系统中，如果X满足以下三个条件，则X是（A，Con(1) X=X，(2) <$F <$X，<$y ∈ Con和y <$X，s.t. 很抱歉，120M. Wu et al. /Electronic Notes in Theoretical Computer Science 301（2014）117(3) 且y ∈ X，s.t. 是的。对于一般代数信息系统，关于集合包含，A的状态形成偏序集，它们表示为|一|.直觉上，对于一个信息系统（A，Con，Con），集合A应该被认为是给出关于数据的信息的原子命题，而一个由有限个相互一致的集合（即：e.不矛盾的命题。 此外，蕴涵关系告诉我们哪些命题可以从什么推导出来。一般代数信息系统是代数论域的具体表示。命题2.2 [14]设（A，Con，n）是一般代数信息系统，则|一|是一个代数域。定义2.3设L是一个代数整环。那么一般的代数信息系统IS（L）可以构造如下：(i) A=L，(ii) Con={x|x±A，x指向≤（a≤b，如果a= b或ab）}，(iii) 若x∈Con，则x∈a惠（b∈x）ab.命题2.4设L是一个代数整环。则L是阶同构于|.|.3AL信息系统在这一部分中，我们引入了代数信息系统的概念.我们构造代数信息系统的方法与Spreen的方法不同，因为我们是基于代数域的基来构造代数信息系统的。我们还得到了AL信息系统与代数域之间的一个双射对应。定义3.1设A是一个集合，Con是A的一个非空有限子集的集合，并且Con×A。则一个代数信息系统（简称AL信息系统）是一个三元组（A，Con，n），并且下列规则对所有集合x，y∈Con，元素a，b∈A成立。(1) {a}∈Con，(2) x<$a <$x{a}∈Con，(3) a∈x < $x <$a，(4) xy和y a x a。其中x ∈ y意味着对所有b ∈ y，x ∈ b。在AL信息系统中， 对于任何子集XA， X：= {a∈A|（<$x±X）x<$a}。M. Wu et al. /Electronic Notes in Theoretical Computer Science 301（2014）117121xi1∈A，xi2∈A，则xi1xi2±X，根据X的性质，存在x，从AL推理系统的规则（1）出发，我们只需要证明X=A。如果定义3.2如果X满足以下两个条件，则X是（A，Con，n）的状态：1. X=X，2. <$F±X，<$y±X和y∈Con，使得y<$F。由于我们定义了AL信息系统的状态，关于集合包含，A的状态形成一个偏序集，我们表示为|一|. （2）第（3）段 我们可以很容易地证明状态条件（2）等价于<$F<$X，<$z±X和z∈Con，使得F<$z. 注意，如果X ∈|一|，y∈ Con且y ± X，则检验y <$X是平凡的。在下面的步骤中，我们证明了AL信息系统（A，Con，Con）的状态是一个代数域。提案3.3|一|是个DCPO证据 设D={Xi}i∈I是|一|且X= i∈IX i. 如果a∈X，根据状态的定义，存在x±X，使得x≠a。对x±X，D是有向的，存在i0∈I使得x<$Xi0. 由于X i0∈|一|，所以a∈Xi 0<$X，我们得到X=X。 如果F是X的任意有限集，因为{Xi}i∈I是有向的，则存在i1∈I使得F<$Xi1。由于X i1∈|一|，所以y∈Con且y±Xi1使得y<$F，也是y±X. 我们已经完成了证明。Q命题3.4设（A，Con，n）是AL信息系统，x∈Con.然后（1）x∈|一|.（2）A的子集X是状态当且仅当存在{xi}i∈I∈Con使得{xi}i∈I是有向的且X=i∈I xi。证据 根据AL信息系统的规则（4），我们可以很容易地得到任何y∈Con，y=y，所以x满足状态的条件（1）。 由于x也满足条件（2）的状态是明显的，因为x ∈ a，对于任何a ∈ x，它意味着x ∈|一|.接下来，假设一个集合{x i}i∈I∈Con，{x i}i∈I是有向的，并且X=i∈Ix i.如果y1±X和y1<$a，因为{xi}i∈I是有向的，则存在i1∈I，使得y1<$xi1。这意味着a∈x i1<$X，所以X=X。如果<$F±X，则存在i2∈I，使得F<$xi2，因此xi2<$F和xi2<$X。 通过上述步骤，我们得到X∈|一|.相反，假设X ∈|一|，考虑族A ={x |x ∈ Con且x <$X}。即x±X和x <$xi1xi2。 这意味着x是xi1，xi2的上界，所以A是定向的。Q推论3.5设A是AL信息系统，则对任意状态X，XJ∈|一|、XXJ惠（<$x∈Con）X<$x<$XJ因此，|一|是x（x∈ Con）。122M. Wu et al. /Electronic Notes in Theoretical Computer Science 301（2014）117∈JJJ。由于x<$x<$XJ<$j∈JXj，存在j0∈J，使得x<$Xj0，所以X<$x<$证据设X，XJ∈|一|，XXJ.根据命题3.4，XJ=iIxi（xi∈Con且xi±XJ）。 由于{xi}i∈I是有向的，存在i0∈ I使得X <$xi0，因此X<$xi0<$X。 公司;公司因此，补充XXX，和Xj∈JXj（Xj∈|一|）.Xj0. 这意味着XXJ。Q定理3.6设A是AL信息系统.然后|一|是一个代数域。相反，对于任何代数域（L，≤），我们可以构造一个AL信息系统IS（L）如下：(i) A=K（L），(ii) Con={x|且x有最大元素}，(iii) 若x ∈ Con，则x ∈ a惠a ∈↓ x。则L是阶同构于|IS（L）|.证据我们很容易证明|一|是一个代数域使用上述结论。现在我们来证明第二部分。设L是一个代数整环，考虑IS（L）=（K（L），Con，n）. 在《易经》中，有一句话叫做：“以物易物，以物易物。 假设x∈Con，x<$a，则根据定义，x有一个最大元素b且a∈↓x=↓b，因此b是x<$a中的最大者，因此x<${a}∈Con。设x∈Con，a∈x，则a∈↓x，因此x<$a。如果x，y∈Con，x<$b对所有b∈y，这意味着y<$↓x。如果y<$a，则a∈<$y<$$>x，因此x<$a。现在我们只需要证明IS（L）是AL信息系统。证明了对K（L）的任意子集X，它是IS（L）的一个状态当且仅当存在（K（L），≤）的某个有向子集{bi}i∈I，使得X=i∈I{↓bi}：一方面，假设X是IS（L）的一个状态。 对于任何F±X，根据X的定义，存在X的子集x，x ∈ Con且x <$F。 根据IS（L）的定义，x有一个最大元素a，F<$x=<$a，所以a是F的上界，这意味着X是有向的。如果b≤c∈X，则{c}<$b，因此b∈X，这意味着X是一个下集，soX=b∈X{↓b}。另一方面，如果{bi}i∈I是K（L）中的有向集，X=i∈I{↓bi}。 F或a nyx∈Con，x<$X，x<$a惠a∈↓x<$a∈X，s o X=X.对于任意的F±X，由于{bi}i∈I是有向集，存在一个bio∈{bi}i∈Isuch那个Fbio。 通过定义IS（L），{bio} ∈Cn，{bio} ∈F，X是IS（L）的一个状态.（L，≤）与|IS（L）|从代数域的定义可以直接得出。Q我们的AL信息系统有一些好处：(1) 简要定义和规则：我们的代数信息系统规则和状态条件比一般的代数信息系统简洁，易于构造和操作。(2) 我们可以在代数论域的基础上直接构造人工智能信息系统。(3) 方便的推广：在我们的AL信息系统的基础上，我们可以得到代数整环子类的一些简洁的信息系统。我们的代数信息系统不同于一般的代数信息系统M. Wu et al. /Electronic Notes in Theoretical Computer Science 301（2014）117123并具有一些优势。我们在下面的例子中展示它们例 3.7 设 L 是 一 个 代 数 整 环 ， L = （ a1 ， a2 ， a3 ， ···an ， ··· ， T ） 且a1

下载后可阅读完整内容，剩余1页未读，立即下载