Regular Language Representations in the Constructive Type Theory of Coq

We explore the theory of regular language representations in the constructive type theory of Coq. We cover various forms of automata (deterministic, nondeterministic, one-way, two-way), regular expressions, and the logic WS1S. We give translations between all representations, show decidability results, and provide operations for various closure properties. Our results include a constructive decidability proof for the logic WS1S, a constructive refinement of the Myhill-Nerode characterization of regularity, and translations from two-way automata to one-way automata with verified upper bounds for the increase in size. All results are verified with an accompanying Coq development of about 3000 lines.     

针对教学场景的ZFC集合论Coq形式化

离散数学是计算机类专业的基础课程之一,命题逻辑、一阶逻辑与公理集合论是其重要组成部分.教学实践表明,初学者准确理解语法、语义、推理系统等抽象概念是有一定难度的.近年来,已有一些学者开始在教学中引入交互式定理证明工具,以帮助学生构造形式化证明,更透彻地理解逻辑系统.然而,现有的定理证明器有较高上手门槛,直接使用会增加学生的学习负担.鉴于此,在Coq中开发了针对教学场景的ZFC公理集合论证明器.首先,形式化了一阶逻辑推理系统和ZFC公理集合论;之后,开发了数条自动化推理规则证明策略.学生可以在与教科书风格相同的简洁证明环境中使用自动化证明策略完成定理的形式化证明.该工具被用在了大一新生离散数学课程的教学中,没有定理证明经验的学生使用该工具可以快速完成数学归纳法和皮亚诺算术系统等定理的形式化证明,验证了该工具的实际效果.     

Coq Formalization of ZFC Set Theory for Teaching Scenarios

Discrete mathematics is a foundation course for computer-related majors, and propositional logic, first-order logic, and the axiomatic set theory are important parts of this course. Teaching practice shows that beginners find it difficult to accurately understand abstract concepts, such as syntax, semantics, and reasoning system. In recent years, some scholars have begun introducing interactive theorem provers into teaching to help students construct formal proofs so that they can understand logic systems more thoroughly. However, directly employing the existing theorem provers will increase students'' learning burden since these tools have a high threshold for getting started with them. To address this problem, we develop a prover for the Zermelo-Fraenkel set theory with the axiom of Choice (ZFC) in Coq for teaching scenarios. Specifically, the first-order logical reasoning system and the axiomatic set theory ZFC are formalized, and several automated proof tactics specific to reasoning rules are then developed. Students can utilize these automated proof tactics to construct formal proofs of theorems in a textbook-style concise proving environment. This tool has been introduced into the teaching of the course of discrete mathematics for freshmen. Students with no prior theorem-proving experience can quickly construct formal proofs of theorems including mathematical induction and Peano arithmetic with this tool, which verifies the practical effectiveness of this tool.     

Optimizing Epochal Evolutionary Search: Population-Size Dependent Theory

Epochal dynamics, in which long periods of stasis in an evolving population are punctuated by a sudden burst of change, is a common behavior in both natural and artificial evolutionary processes. We analyze the population dynamics for a class of fitness functions that exhibit epochal behavior using a mathematical framework developed recently, which incorporates techniques from the fields of mathematical population genetics, molecular evolution theory, and statistical mechanics. Our analysis predicts the total number of fitness function evaluations to reach the global optimum as a function of mutation rate, population size, and the parameters specifying the fitness function. This allows us to determine the optimal evolutionary parameter settings for this class of fitness functions.We identify a generalized error threshold that smoothly bounds the two-dimensional regime of mutation rates and population sizes for which epochal evolutionary search operates most efficiently. Specifically, we analyze the dynamics of epoch destabilization under finite-population sampling fluctuations and show how the evolutionary parameters effectively introduce a coarse graining of the fitness function. More generally, we find that the optimal parameter settings for epochal evolutionary search correspond to behavioral regimes in which the consecutive epochs are marginally stable against the sampling fluctuations. Our results suggest that in order to achieve optimal search, one should set evolutionary parameters such that the coarse graining of the fitness function induced by the sampling fluctuations is just large enough to hide local optima.     

新型气液联合液压打桩锤的仿真研究

液压系统是液压打桩锤的核心部分,其性能直接影响液压打桩锤打桩的质量及打桩效率.为了建立系统主要插装阀及桩锤系统的数学模型,并运用AMESim建立了仿真模型,根据液压系统的工作原理运用AMESim对新型气液联合打桩锤的动态过程进行了仿真研究.结果表明系统的最大打击能,最大冲击力和频率等参数均符合设计要求,通过对插装阀启闭时的响应时间及锤头下降时间的比较,系统也可以实现一定条件下的急停.仿真结果对于新型气液联合液压打桩锤的研究和开发具有一定的指导意义.     

Nominal Reasoning Techniques in Coq: (Extended Abstract)

We explore an axiomatized nominal approach to variable binding in Coq, using an untyped lambda-calculus as our test case. In our nominal approach, alpha-equality of lambda terms coincides with Coq's built-in equality. Our axiomatization includes a nominal induction principle and functions for calculating free variables and substitution. These axioms are collected in a module signature and proved sound using locally nameless terms as the underlying representation. Our experience so far suggests that it is feasible to work from such axiomatized theories in Coq and that the nominal style of variable binding corresponds closely with paper proofs. We are currently working on proving the soundness of a primitive recursion combinator and developing a method of generating these axioms and their proof of soundness from a grammar describing the syntax of terms and binding.     

Formalizing non-interference for a simple bytecode language in Coq

In this paper, we describe the application of the interactive theorem prover Coq to the security analysis of bytecode as used in Java. We provide a generic specification and proof of non-interference for bytecode languages using the Coq module system. We illustrate the use of this formalization by applying it to a small subset of Java bytecode. The emphasis of the paper is on modularity of a language formalization and its analysis in a machine proof. C. B. Jones     

Research on Theory of Green Product DesignAutomation

Facing with the design activihes of low efficacy and low standard on design automationdue to the probabilishc, non-rational and non-standard product design. This Paper puts forward thetheory of generalized mapping, which is proved to be effective in the enhancemed of the creativity ofproduct design automation. It further explores the applicahon and progress in the creative greenproduct conceptual and detail design.     

自动化测试用例测试失败类型分析

随着计算机技术的发展,软件迭代开发模式在软件开发与测试过程中占的比重越来越大。软件迭代开发过程中大量采用自动化测试,在测试环境上进行测试脚本连跑;通常会有一定数量的测试脚本失败,需要对这些脚本进行失败分析。这是一项十分重要的工作,否则软件产品无法继续开发,也无法保证软件产品的质量。依据软件迭代开发和测试工作实践,归纳总结了自动化测试用例失败的类型,介绍了各种类型测试脚本失败的工作实例;叙述了自动化测试用例失败分析涉及的角色和软件迭代开发过程中自动化测试应用场景;详细叙述了自动化测试用例失败的定位和分析处理;最后叙述了测试工作的改进。工作实践表明做好软件自动化测试用例失败分析工作,有助于提高软件产品开发效率和提升软件产品质量。     

Tilting at Windmills with Coq: Formal Verification of a Compilation Algorithm for Parallel Moves

This article describes the formal verification of a compilation algorithm that transforms parallel moves (parallel assignments between variables) into a semantically-equivalent sequence of elementary moves. Two different specifications of the algorithm are given: an inductive specification and a functional one, each with its correctness proofs. A functional program can then be extracted and integrated in the Compcert verified compiler.     

多旋翼飞控推进子系统的Coq形式化验证

飞行器需要高可靠的飞行控制系统软件(飞控)来控制其运行.在传统开发模式下,先由人工将领域知识描述为自然语言形式的模型,再根据模型手动编写代码,然后使用软件测试技术来排除软件错误,这种模式由于人工易出错、自然语言存在二义性、测试技术的不完备性,导致难以构建出高可靠的飞控软件.基于形式验证技术的新型软件开发方法可从多方面提高飞控系统的可靠性.使用Coq定理证明器对全权提出的多旋翼飞控推进子系统进行了完整的形式验证,生成了一个可用的高可靠函数式软件库.主要工作有:首先将领域知识整理为具有层次结构以适合进行形式验证的文档,分离了基本函数和复合函数,并提出最简形式函数概念;再根据该文档进行形式化描述,定义常量、变量、基本函数、复合函数、最简形式函数和公理等;其次对各类导出函数的推导正确性建立为引理并予以证明;再次对多旋翼最长悬停时间等实际问题给出了求解算法;最后利用Coq程序抽取功能生成了OCaml语言的函数式软件库.后续将对飞控更多子系统进行基于形式验证的开发,并最终建立完整的经形式化验证的高可靠飞控系统.     

矿井通风机选型设计系统的自动化

针对传统的矿井通风机选型方式存在选型设计周期长、设计精度不高、不能保存设计方案、选型过程书写繁琐等问题,提出了一种软件实现的矿井通风机选型设计系统的设计方案,介绍了该系统的基本功能模块设计、设计流程及实现的关键技术。该系统以最小二乘法为基础,采用LONGRUAN GIS 3.0平台及Access数据库,实现了通风机型号参数的计算、通风机性能曲线的输出、通风机工况点的自动计算、通风机选型报告的自动生成、通风机选型方案的存储及查询等功能。     

Type Theory and Language Constructs for Objects with States

In current class-based Object-Oriented Programming Languages (OOPLs), object types include only static features. How to add object dynamic behaviors modeled by Harel's statecharts into object types is a challenging task. We propose adding states and state transitions, which are largely unstated in object type theory, into object type definitions and typing rules. We argue that dynamic behaviors of objects should be part of object type definitions. We propose our type theory, the τ-calculus, which refines Abadi and Cardelli's ζ-calculus, in modeling objects with their dynamic behaviors. In our proposed type theory, we also explain that a subtyping relation between object types should imply the inclusion of their dynamic behaviors. By adding states and state transitions into object types, we propose modifying programming language constructs for state tracking.     

基于Coq的RVWMO加载值公理形式化描述与推论证明

RISC-V内存一致性模型（RVWMO）规定了RISC-V多核系统的访存序约束,是RISC-V软硬件设计者共同遵守的重要规范,旨在为硬件设计提供灵活性的同时保证软件的易开发性。RISC-V指令集规范使用全局访存序、保留程序序以及三条公理（加载值公理、原子公理与进度保证公理）描述RVWMO。通过运用RVWMO的规则,可对多线程程序的访存序合法性进行判定,进而指导芯片设计、验证与软件开发。其中,加载值公理是最为复杂和难以运用的规则之一,是多个典型案例合法性判定的重要基础。然而,规范对于该公理的描述及案例讲解主要基于自然语言,缺乏清晰严格的形式化描述和推理过程,不利于读者理解和运用该公理。本文基于交互式定理辅助证明工具Coq,给出了RVWMO加载值公理的形式化描述以及相关引理、定理和推论的证明,对于理解运用RVWMO加载值公理和判定访存序的合法性具有重要意义。     

Habitation: A Domain-Specific Language for Home Automation

Developers need suitable tools to develop home automation systems while enhancing quality and productivity. One solution is to use domain-specific languages (DSLs) within a model-driven approach. The Habitation DSL provides a powerful visual development environment, including a catalog of reusable functional units and a set of home automation interconnection primitives. The model-driven approach offers mechanisms to automatically generate code to enhance the quality and portability of home automation systems. The result is an Eclipse-based tool whose usability the authors have validated in a case study.     

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