The logic of message-passing

Message-passing is a key ingredient of concurrent programming. The purpose of this paper is to describe the equivalence between the proof theory, the categorical semantics, and term calculus of message-passing. In order to achieve this we introduce the categorical notion of a linear actegory and the related polycategorical notion of a poly-actegory. Not surprisingly the notation used for the term calculus borrows heavily from the (synchronous) π-calculus. The cut-elimination procedure for the system provides an operational semantics.     

Proofs of randomized algorithms in Coq

Randomized algorithms are widely used for finding efficiently approximated solutions to complex problems, for instance primality testing and for obtaining good average behavior. Proving properties of such algorithms requires subtle reasoning both on algorithmic and probabilistic aspects of programs. Thus, providing tools for the mechanization of reasoning is an important issue. This paper presents a new method for proving properties of randomized algorithms in a proof assistant based on higher-order logic. It is based on the monadic interpretation of randomized programs as probabilistic distributions (Giry, Ramsey and Pfeffer). It does not require the definition of an operational semantics for the language nor the development of a complex formalization of measure theory. Instead it uses functional and algebraic properties of unit interval. Using this model, we show the validity of general rules for estimating the probability for a randomized algorithm to satisfy specified properties. This approach addresses only discrete distributions and gives rules for analyzing general recursive functions.We apply this theory to the formal proof of a program implementing a Bernoulli distribution from a coin flip and to the (partial) termination of several programs. All the theories and results presented in this paper have been fully formalized and proved in the Coq proof assistant.     

Ambient演算的一种分层语义

网络计算系统中涉及的操作复杂,很难直接给出一种的语义描述框架.作为一种网络计算模型,Ambient演算主要刻画了计算的分布性和移动性.目前关于Ambient的语义研究很多,但均是基于规约规则的语义形式.这种描述方式尽管简洁,一方面却具有不确定性,不利于实际的网络计算系统的设计和直接实现;另一方面,这种语义描述方式均在一个层次上描述Ambient演算系统中的各种行为语义,使得Ambient演算中各种计算行为纠缠在一起,复杂而难以理解.根据Ambient演算的结构特点,给出了Ambient演算的一种分层语义描述形式,系统以ambient为单元,分成3层进行描述,分别给出不同层上行为的语法定义、语义定义、语义方程以及不同层间的转换函数的定义,从而给出Ambient演算系统的指称语义描述形式.这种描述方式从层次化的角度分析了Ambient演算的计算行为,有助于对Ambient演算中行为的理解和实际应用系统的实现.     

面向本体的服务组合差分进化策略

针对目前Web服务描述服务功能的语义不够深入而使服务识别组合能力欠佳的问题,提出一种面向本体的语义服务功能描述方法,建立本体间的映射关系模型和服务质量关系模型,通过改进差分进化算法求解,得到一种较好的服务组合识别方法。在九寨沟旅游管理信息系统中的应用表明,该方法比传统的方法优越。     

基于层次语义的Web服装图像智能采集方法

以大规模智能采集互联网中的服装图像为目的,研究如何利用互联网上服装图像的伴随文本与服装图像概念之间的关联,实现自动采集各语义对应的服装图像。在HITS(Hyperlink-Induced Topic Search)算法的基础上提出一个基于层次语义的图像采集算法SICR(Semantic-based Image Collection Robot)。该算法在层次语义库的支持下,扩充根集与去除链接工厂页面同步进行。在爬取链接网页前,进行锚文字的相似度计算和页面内容的概念分析,舍弃不符合语义的页面,只下载满足语义的服装图像。算法克服了基于文本分析或链接分析的图像自动提取算法的不足,具有较高的准确率和召回率,实验结果证明了SICR算法的有效性。     

基于语义与规则的有标复句层次体系研究

汉语复句层次关系分析是中文信息处理领域极具挑战性的课题之一。为解决关系词标识信息不充足所导致的复句层次关系识别准确率下降问题,挖掘了影响分句关联的形式化语义知识,在此基础上构建了小句关联体识别算法并将其应用于相应的复句层次判定规则之中,以辅助分析其层次关系;对于其余单、多重有标复句的层次识别,使用基于搭配规则的移进-归约算法;最后提出了一种语义与规则相结合的复句层次分析模型。实验结果表明,此方法在一定程度上提高了复句层次关系识别的准确率。     

一种命令式风格的面向对象语言语义框架

面向对象语言在软件工程实践中有着广泛的应用。为面向对象语言定义严格的语义有助于理解面向对象语言的本质特征,对验证软件、提高软件系统可靠性等也具有重要意义。给出了一种新的面向对象语言的语义框架,该框架基于命令式的风格,具有操作语义和类型规则;证明了该语义框架的类型安全定理。     

Abstract processes of place/transition systems

A well-known problem in Petri net theory is to formalise an appropriate causality-based concept of process or run for place/transition systems. The so-called individual token interpretation, where tokens are distinguished according to their causal history, giving rise to the processes of Goltz and Reisig, is often considered too detailed. The problem of defining a fully satisfying more abstract concept of process for general place/transition systems has so-far not been solved. In this paper, we recall the proposal of defining an abstract notion of process, here called BD-process, in terms of equivalence classes of Goltz-Reisig processes, using an equivalence proposed by Best and Devillers. It yields a fully satisfying solution for at least all one-safe nets. However, for certain nets which intuitively have different conflicting behaviours, it yields only one maximal abstract process. Here we identify a class of place/transition systems, called structural conflict nets, where conflict and concurrency due to token multiplicity are clearly separated. We show that, in the case of structural conflict nets, the equivalence proposed by Best and Devillers yields a unique maximal abstract process only for conflict-free nets. Thereby BD-processes constitute a simple and fully satisfying solution in the class of structural conflict nets.