程序语言中基于Fibrations理论的索引共归纳数据类型

传统范畴论与共代数等方法在分析语义行为与描述共归纳规则方面存在不足,应用Fibrations理论对程序语言中索引共归纳数据类型(indexed co-inductive data type,ICDT)进行了研究。通过基变换构造索引Fibration,建立索引Fibration的等式函子与商函子等工具,应用伴随性质与保持等式的提升深入分析ICDT的语义行为;以此为基础,构造ICDT上参数化的共递归操作,在Fibrations理论框架内抽象描述具有普适意义的共归纳规则,并以实例分析简要介绍Fibrations理论在ICDT中的应用。与传统研究方法相比,Fibrations理论具有简洁的描述性与灵活的扩展性,可以精确分析ICDT的语义行为,具有高度的抽象性且不依赖特定的计算环境,描述了ICDT具有普适意义的共归纳规则。     

基于Fibrations理论的共享系统数据模型

传统共享系统数据模型的建模方法在语义性质分析和语义行为描述方面存在不足,针对以上问题提出了一种基于Fibrations理论的共享系统数据模型。主要工作体现在两个方面:首先,应用真值函子、保持真值的提升与内涵函子并结合代数方法精确分析了语义性质,应用等式函子、保持等式的提升及商函子并结合共代数方法形式化描述了语义行为;其次,在Fibrations理论框架内构造复杂归纳与共归纳数据结构上参数化的递归与共递归操作,抽象描述具有普适意义的归纳与共归纳规则,结合实例简要介绍了Fibrations理论的应用。相对于范畴论等传统方法,简洁描述与灵活扩展的Fibrations理论对共享系统数据模型的语义性质和语义行为进行了精确分析与形式化描述,抽象描述了复杂数据结构具有普适性的归纳与共归纳规则。     

Fibrations理论在索引归纳数据类型不确定语义中的应用

应用Fibrations理论对索引归纳数据类型的不确定语义计算进行了研究。论证了索引范畴的构造,提出了索引Fibration及其真值函子与内涵函子,建立了索引范畴上自函子的一种保持真值的提升,提出了部分F-代数的定义,并应用折叠函数等工具抽象描述了索引归纳数据类型不确定语义计算,辅以实例进行了简要分析,最后通过相关工作的论述指出了Fibrations理论研究方法的优势。     

程序语言中的共归纳数据类型及其应用

归纳数据类型利用代数方法从构造的角度归纳地描述数据类型的有限语法结构,但在描述动态行为方面存在一定的不足。作为归纳数据类型的范畴对偶概念,共归纳数据类型利用共代数方法从观察的角度共归纳地描述了数据类型的动态行为。首先,从范畴论和代数的角度给出程序语言中的归纳数据类型定义,并分析了相应的递归操作;接着,利用共代数给出共归纳数据类型的范畴论定义,并根据共归纳数据类型的终结性分析了相应的共递归操作;最后,指出如何利用无双代数及分配律将归纳与共归纳数据类型有机地融合起来,探讨数据类型的语法构造与动态行为关系。     

Fibrations理论在索引归纳数据类型语法构造中的应用

应用Fibrations理论对索引归纳数据类型的语法构造进行了研究。提出了索引fibration及其真值与内涵函子的定义,构造了索引与代数范畴,利用折叠函数与伴随函子等工具构造了索引范畴中一类相对复杂的索引归纳数据类型,辅以实例进行了简要分析,并通过相关工作的论述指出了Fibrations理论研究方法的优势。     

归纳数据类型的范畴论方法

归纳数据类型是类型论研究的重要分支,传统的数理逻辑或代数方法侧重于描述归纳数据类型的有限语法构造,在语义性质与归纳规则的分析与设计方面存在一定的不足.基于范畴论的方法,在集合范畴的框架内给出谓词的形式化定义,分析谓词范畴与代数范畴的构成与性质,并探讨集合范畴上自函子到谓词范畴上自函子的提升,最后利用伴随函子及其伴随性质深入分析了归纳数据类型具有普适意义的归纳规则.     

计算机科学中的范畴数据类型的研究综述

范畴数据类型是指以范畴论为数学理论基础研究数据类型的描述、计算、语义和应用。早期的范畴数据类型研究以归纳数据类型为主,采用代数从归纳的角度研究有限数据类型的构造语义和递归性质。近年来,归纳数据类型的对偶概念——共归纳数据类型逐渐引起计算机科学工作者的关注与研究,他们采用共代数从观察的角度研究无限数据类型的行为语义和共递归性质。利用范畴论可以为数据类型研究提供统一的数学理论基础,并将代数和共代数中的各种重要研究成果有机地融合在一起,如语法构造与动态行为、递归与共递归、同余与互模拟等。目前,范畴数据类型已经在程序语言、计算描述、理论证明器和并行计算等领域得到广泛的应用。对范畴数据类型的基本概念、数学理论基础、逻辑基础及应用等方面的最新研究成果进行介绍,以引起国内外相关研究领域的学者对计算机科学中的范畴数据类型理论的关注。     

类型化π演算的双代数语义

证明互模拟同余通常冗长且易出错.双代数为解决该问题提供统一的框架:若行为函子保持弱回拉,共代数范畴到基范畴的忘却函子有右伴函子,则最大共代数互模拟同余.但已有双代数理论建模类型化π演算存在以下困难:行为函子不保持弱回拉,进程互模拟与共代数互模拟不一致.为解决以上两个问题,用稠密拓扑导出布尔范畴作为语义范畴,令行为函子保持弱回拉;定义一类行为函子,使最大进程互模拟与最大共代数互模拟一致,而迟语义和早语义对应的行为函子属于该类函子.进而给出π演算最大进程互模拟同余的双代数模型,为进一步应用双代数框架对其他复杂演算建模奠定了理论基础.     

计算机科学中的共代数方法的研究综述

代数理论已经在抽象数据类型、程序语义等计算机科学领域有了广泛的应用,而代数的对偶概念--共代数,则直到20世纪90年代中后期才被越来越多的计算机学者关注.代数从"构造"的角度研究数据类型,而共代数则从"观察"的角度考察系统及其性质.共代数方法对研究基于状态的系统有独特的优越性,可以对系统的行为等价、不确定性等从数学上进行深入的探讨.目前,共代数理论已经逐步应用在自动机理论、并发程序的语义、面向对象程序的规范等领域.对共代数的基本概念、范畴理论基础、共代数逻辑及应用等方面的最新研究成果进行了介绍,以引起国内相关研究领域的学者对计算机科学中的共代数方法的关注.     

抽象数据类型的双代数结构及其计算

程序语言中的许多抽象数据类型包含了可递归定义的语法构造和可共递归定义的动态行为特征,因此单纯利用代数或共代数难以给出完整的描述.双代数是同一载体集上的代数和共代数对,提供了一种从范畴论的角度探讨抽象数据类型上的语法构造和动态行为关系及性质的可行途径.给出抽象数据类型的双代数结构,并利用代数函子对共代数函子的分配律描述了语法构造与动态行为之间的自然转换关系;利用分配律对共代数和代数函子进行函子化提升,给出一种构造初始代数(或终结共代数)上的共代数(或代数)结构,并将其提升为初始(或终结)λ-双代数的方法.在此基础上,进一步将函子化提升应用于各种递归(包括迭代和原始递归)及共递归函数(包括共迭代和原始共递归)的定义及计算中,并给出相应的计算定律.     

Certifying circuits in Type Theory

We investigate how to take advantage of the particular features of the calculus of inductive constructions in the framework of hardware verification. First, we emphasize in a short case study the use of dependent types and of the constructive aspect of the logic for specifying and synthesizing combinatorial circuits. Then, co-inductive types are introduced to model the temporal aspects of sequential synchronous devices. Moore and Mealy automata are co-inductively axiomatized and are used to represent uniformly both the structures and the behaviors of the circuits. This leads to clear, general and elegant proof processes as is illustrated on the example of a realistic circuit: the ATM Switch Fabric. All the proofs are carried out using Coq.Accepted in revised form 29 February 2004 by C.B. Jones     

基于负样本精简概念格规则的语义概念检测

为挖掘视频中丰富的语义信息,提出基于负样本精简概念格规则的语义概念检测方法.分析基于概念格的语义分析系统,考虑训练数据中负样本的信息,提出利用负样本精简的语义规则提取算法,将其应用于视频语义检测.先将视频镜头的低层特征映射到低层语义特征,再利用该算法生成语义分类规则,进行视频语义概念检测.实验结果表明,该方法是有效可行...     

Marking up in TATOE and exporting to SGML

This paper presents a method for developing limited-context grammar rules in order to mark up text automatically, by attaching specific text segments to a small number of well-defined and application-determined semantic categories. The Text Analysis Tool with Object Encoding (TATOE) was used in order to support the iterative process of developing a set of rules as well as for constructing and managing the lexical resources. The work reported here is part of a real-world application scenario: the automatic semantic mark up of German news messages, as provided by a German press agency, according to the SGML-based standard News Industry Text Format (NITF) to facilitate their further exchange. The implemented export mechanism of the semantic mark up into NITF is also described in the paper. This revised version was published online in July 2006 with corrections to the Cover Date.     

Modeling with the semantic Web in the geosciences

Earth system science deals with complex systems that pose many significant representation challenges. Ontologies as knowledge repositories have been developed to support the primary goal of sharing knowledge in a manner that aids understanding. DARPA is currently developing an extension to OWL called SWRL (semantic Web rule language), which lets to express some aspects of rules and process behaviors. The semantic Web facilitates researchers' collaboration and model components automated discovery and use. Spatial data plays a key role in modeling the earth system as the input to models and as a measure against which results are validated.     

CoCasl at Work — Modelling Process Algebra

CoCasl[11], a recently developed coalgebraic extension of the algebraic specification language Casl[2], allows for modelling systems in terms of inductive datatypes as well as of co-inductive process types. Here, we demonstrate how to specify process algebras, namely CCS[10] and CSP[8,17], within such an algebraic-coalgebraic framework. It turns out that CoCasl can deal with the fundamental concepts of process algebra in a natural way: The type system of communications, the syntax of processes and their structural operational semantics fit well in the algebraic world of Casl, while the additional coalgebraic constructs of CoCasl cover the various process equivalences (bisimulation, weak bisimulation, observational congruence, and trace equivalence) and provide fully abstract semantic domains. CoCasl hence becomes a meta-framework for studying the semantics and proof theory of reactive systems.     

基于混合语言信息的词语搭配倾向判别方法

具有较强褒贬倾向的词语搭配对于文本的情感分析具有重要的价值。该文提出了一种混合语言信息的词语搭配的倾向判别方法。该方法首先根据词语搭配六种模式的特点,确定出各模式的概率潜在语义模型,然后利用这些语义模型判别搭配的情感倾向。最后对部分包含情感词的搭配再利用规则修正其先前标注的情感倾向。基于汽车语料的实验结果表明,基于混合语言信息的词语搭配情感倾向判别方法优于单纯基于概率潜在语义模型或规则的方法。     

基于多视角的多类型错误全面检测方法

随着信息化社会的发展,数据的规模越发庞大,数据的种类也越发丰富.时至今日,数据已经成为国家和企业的重要战略资源,是科学化管理的重要保障.然而,随着社会生活产生的数据日益丰富,大量的脏数据也随之而来,数据质量问题油然而生.如何准确而全面地检测出数据集中所包含的错误数据,一直是数据科学中的痛点问题.尽管已有许多传统方法被广泛用于各行各业,如基于约束与统计的检测方法,但这些方法通常需要丰富的先验知识与昂贵的人力和时间成本.受限于此,这些方法往往难以准确而全面地检测数据.近年来,许多新型错误检测方法利用深度学习技术,通过时序推断、文本解析等方式取得了更好检测效果,但它们通常只适用于特定的领域或特定的错误类型,面对现实生活中的复杂情况,泛用性不足.基于上述情况,结合传统方法与深度学习技术的优点,提出了一个基于多视角的多类型错误全面检测模型CEDM.首先,从模式的角度,结合现有约束条件,在属性、单元和元组层面进行多维度的统计分析,构建出基础检测规则;然后,通过词嵌入捕获数据语义,从语义的角度分析属性相关性、单元关联性与元组相似性,进而基于语义关系,从多个维度上更新、扩展基础规则;最终,联合多个视角...