• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual ACM/IEEE Symposium on Logic in Computer Science >Duality in Computer Science *
【24h】

Duality in Computer Science *

机译：计算机科学的双重性 *

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This is a paper on Stone duality in computer science with special focus on topics with applications in formal language theory. In Section 2 we give a general overview of Stone duality in its various forms: for Boolean algebras, distributive lattices, and frames. For distributive lattices, we discuss both Stone and Priestley duality. We identify how to move between the different dualities and which dual spaces carry the Scott topology. We then focus on three themes.The first theme is additional operations on distributive lattices and Boolean algebras. Additional operations arise in denotational semantics in the form of predicate transformers. In verification they occur in the form of modal operators. They play an essential rôle in Eilenberg's variety theorem in the form of quotient operations. Quotient operations are unary instantiations of residual operators which are dual to the operations in the profinite algebras of algebraic language theory. We discuss additional operations in Section 3. The second theme is that of hyperspaces, that is, spaces of subsets of an underlying space. Some classes of algebras may be seen as the class of algebras for a functor. In the case of predicate transformers the dual functors are hyperspace constructions such as the Plotkin, Smyth, and Hoare powerdomain constructions. The algebras-for-a-functor point of view is central to the coalgebraic study of modal logic and to the solution of domain equations. In the algebraic theory of formal languages various hyperspace-related product constructions, such as block and Schützenberger products, are used to study complexity hierarchies. We describe a construction, similar to the Schützenberger product, which is dual to adding a layer of quantification to formulas describing formal languages. We discuss hyperspaces in Section 4.The final theme is that of "equations". These are pairs of elements of dual spaces. They arise via the duality between subalgebras and quotient spaces and have provided one of the most successful tools for obtaining decidability results for classes of regular languages. The perspective provided by duality allows us to obtain a notion of equations for the study of arbitrary formal languages. Equations in language theory is the topic of Section 5.
机译：这是一篇有关计算机科学中的斯通二元性的论文，特别侧重于形式语言理论中的应用主题。在第2节中，我们以各种形式对Stone对偶性进行了总体概述：布尔布尔代数，分布格和框架。对于分布晶格，我们讨论了Stone和Priestley对偶。我们确定了如何在不同的对偶之间移动以及哪些对偶空间承载了斯科特拓扑。然后我们集中讨论三个主题。第一个主题是对分布格和布尔代数的附加运算。附加操作以谓词转换器的形式出现在指称语义上。在验证中，它们以模态运算符的形式出现。它们以商运算的形式在艾伦伯格的变分定理中起着至关重要的作用。商运算是余数运算符的一元实例化，它是代数语言理论的有限代数运算的对偶。我们将在第3节中讨论其他操作。第二个主题是超空间，即基础空间子集的空间。某些类别的代数可能被视为函子的代数类别。对于谓词互感器，双函子是超空间构造，例如Plotkin，Smyth和Hoare幂域构造。 functor的代数观点是模态逻辑的联合代数研究和域方程解的核心。在形式语言的代数理论中，各种与超空间相关的乘积构造（例如块积和Schützenberger乘积）用于研究复杂性层次结构。我们描述了一种类似于Schützenberger产品的构造，它的双重作用是在描述形式语言的公式中增加了一层量化。我们将在第4节中讨论超空间。最后一个主题是“等式”。这些是双重空间元素对。它们是通过子代数和商空间之间的对偶而产生的，并提供了用于获取常规语言类可判定性结果的最成功工具之一。对偶提供的观点使我们能够获得方程式的概念，用于研究任意形式的语言。语言理论中的方程式是第5节的主题。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号