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算法的有效性。     

改进OR1200 CPU流水线的设计

流水线是制造高性能CPU的关键技术,目前被广泛研究的OR1200是一款带有四级流水线的免费开源CPU. 为了提高流水线的效率,针对OR1200没有设计访存流水段,流水线会暂停等待加载存储类指令这个问题,在LSU操作即访存操作模块,为OR1200增加了访存流水段,设计了冒险检测和旁路单元,因此CPU在访存阶段不需要暂停,从而使OR1200变为真正的五级流水线CPU;另一方面,当需要用加载指令加载数据的时候,会导致加载类数据冒险问题,为了解决此类冒险,设计了数据有效信号Tag,用来控制流水线暂停,对乘法计算、访存阶段以及其他不能在执行阶段得到结果的运算作流水线暂停判断,以等待数据的获取. 通过实验仿真证明,Tag信号暂停流水线一个时钟后会把数据反馈回去,成功解决了必须暂停数据相关问题的暂停判断问题.     

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

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

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.     

A semantics for Behavior Trees using CSP with specification commands

In this paper we give a formal definition of the requirements translation language Behavior Trees. This language has been used with success in industry to systematically translate large, complex, and often erroneous requirements documents into a structured model of the system. It contains a mixture of state-based manipulations, synchronisation, message passing, and parallel, conditional, and iterative control structures. The formal semantics of a Behavior Tree is given via a translation to a version of Hoare’s process algebra CSP, extended with state-based constructs such as guards and updates, and a message passing facility similar to that used in publish/subscribe protocols. We first provide the extension of CSP and its operational semantics, which preserves the meaning of the original CSP operators, and then the Behavior Tree notation and its translation into the extended version of CSP.