Autarkic Computations in Formal Proofs

Formal proofs in mathematics and computer science are being studied because these objects can be verified by a very simple computer program. An important open problem is whether these formal proofs can be generated with an effort not much greater than writing a mathematical paper in, say, LATEX. Modern systems for proof development make the formalization of reasoning relatively easy. However, formalizing computations in such a manner that the results can be used in formal proofs is not immediate. In this paper we show how to obtain formal proofs of statements such as Prime(61) in the context of Peano arithmetic or (x+1)(x+1)=x ²+2x+1 in the context of rings. We hope that the method will help bridge the gap between the efficient systems of computer algebra and the reliable systems of proof development.     

Integrating Computer Algebra into Proof Planning

Mechanized reasoning systems and computer algebra systems have different objectives. Their integration is highly desirable, since formal proofs often involve both of the two different tasks proving and calculating. Even more important, proof and computation are often interwoven and not easily separable.In this article we advocate an integration of computer algebra into mechanized reasoning systems at the proof plan level. This approach allows us to view the computer algebra algorithms as methods, that is, declarative representations of the problem-solving knowledge specific to a certain mathematical domain. Automation can be achieved in many cases by searching for a hierarchic proof plan at the method level by using suitable domain-specific control knowledge about the mathematical algorithms. In other words, the uniform framework of proof planning allows us to solve a large class of problems that are not automatically solvable by separate systems.Our approach also gives an answer to the correctness problems inherent in such an integration. We advocate an approach where the computer algebra system produces high-level protocol information that can be processed by an interface to derive proof plans. Such a proof plan in turn can be expanded to proofs at different levels of abstraction, so the approach is well suited for producing a high-level verbalized explication as well as for a low-level, machine-checkable, calculus-level proof.We present an implementation of our ideas and exemplify them using an automatically solved example.Changes in the criterion of rigor of the proof' engender major revolutions in mathematics. H. Poincaré, 1905     

xTras: A field-theory inspired xAct package for mathematica

We present the tensor computer algebra package xTras, which provides functions and methods frequently needed when doing (classical) field theory. Amongst others, it can compute contractions, make Ansätze, and solve tensorial equations. It is built upon the tensor computer algebra system xAct, a collection of packages for Mathematica.     

Overview of software engineering

It is nearly 17 years since the unofficial birth of ‘software engineering’ as a discipline. Mathematics can now be applied to the task of computer programming — turning it into a science. The techniques developed over the period have now matured to an extent where they can be applied in the ‘real world’, rather than just in an academic environment. Mathematics can be used to specify a computer system at a very high level of abstraction, the resultant specification being the computing equivalent of an engineer's blueprint. Such a specification can be used as the basis for developing a computer system, allowing each design decision to be documented and a clear development path charted; thus making maintenance and improvements easier. The exercise of writing a formal specification frequently reveals misconceptions in the minds of both the developer and his customer.Further, the existence of such a specification will allow the verification of the developed software — a mathematical proof of correctness. The development of computer software using formal methods is reviewed, some indication of future trends will be given, and how the ideas of software engineering can be applied today.     

One-unambiguity of regular expressions with numeric occurrence indicators

Regular expressions with numeric occurrence indicators are an extension of traditional regular expressions, which let the required minimum and the allowed maximum number of iterations of subexpressions be described with numeric parameters. We consider the problem of testing whether a given regular expression E with numeric occurrence indicators is 1-unambiguous or not. This condition means, informally, that any prefix of any word accepted by expression E determines a unique path of matching symbol positions in E. One-unambiguity appears as a validity constraint in popular document schema languages such as SGML and XML DTDs (document type definitions) and XML Schema; the last one both includes numeric occurrence indicators and requires one-unambiguity of expressions. Previously published solutions for testing the one-unambiguity of regular expressions with numeric occurrence indicators are either erroneous or require exponential time. The main contribution of this paper is a polynomial-time method for solving this problem, and a formal proof of its correctness.     

一个离散数学辅助教学软件的设计与开发

离散数学是计算机专业的核心基础课程,通常包括逻辑、证明、集合、关系、函数、组合计数、图论和代数等多个模块.一个能求解离散数学问题的计算机软件对离散数学课程的教学和学习都有很好的辅助作用.本文使用面向对象方法设计和开发了一个包含能求解逻辑、集合、组合计数、图论与代数等离散数学课程模块中问题的教学辅助软件.该软件不仅能展示...     

An Overview of a Formal Framework for Managing Mathematics

Mathematics is a process of creating, exploring, and connecting mathematical models. This paper presents an overview of a formal framework for managing the mathematics process as well as the mathematical knowledge produced by the process. The central idea of the framework is the notion of a biform theory which is simultaneously an axiomatic theory and an algorithmic theory. Representing a collection of mathematical models, a biform theory provides a formal context for both deduction and computation. The framework includes facilities for deriving theorems via a mixture of deduction and computation, constructing sound deduction and computation rules, and developing networks of biform theories linked by interpretations. The framework is not tied to a specific underlying logic; indeed, it is intended to be used with several background logics simultaneously. Many of the ideas and mechanisms used in the framework are inspired by the IMPS Interactive Mathematical Proof System and the Axiom computer algebra system.     

Review of generic software for environmental engineering applications

Generic software such as spreadsheet and data base programs provide utilities that can be used to construct routines for various applications. The specific used is determined by the user. Generic software allows interactive programming and data manipulation. These programs have dramatically changed the everyday use of microcomputers by creating an easy and flexible interace ofr inexperienced computer users to create their own user defined routines without requiring any formal programming skills. Data entry and retrieval are extremely easy, as well as transfer of data between different software packages. This paper review some of the commonly used generic software packages, focusing on spreadsheets, data base programs, and integrated software packages for IBM PC compatible microcomputers.Several commercial programs, varying in price and capability, are evaluated to determine their applicability in environmental engineering calculations Evaluations were made in terms of the potential use in engineering calculations and other applications, the mathematical capacity, speed of calculations, versatility, and user friendliness. Data transfer between different programare extremely crucial for engineering applications. It is achieved by using “standard” file formats, such as SIF and DIF files.     

Theorem Prover for Intuitionistic Logic Based on the Inverse Method

The first-order intuitionistic logic is a formal theory from the family of constructive logics. In intuitionistic logic, it is possible to extract a particular example x = a and a proof of a formula P(a) from a proof of a formula ?xP(x). Owing to this feature, intuitionistic logic has many applications in mathematics and computer science. Many modern proof assistants include automated tactics for the first-order intuitionistic logic, which simplify the task of solving challenging problems, such as formal verification of software, hardware, and protocols. In this paper, a new theorem prover (called WhaleProver) for full first-order intuitionistic logic is presented. Testing on the ILTP benchmarking library has shown that WhaleProver performance is comparable with the state-of-the-art intuitionistic provers. Our prover has solved more than 800 problems from the ILTP version 1.1.2. Some of them are intractable for other provers. WhaleProver is based on the inverse method proposed by S.Yu. Maslov. We introduce an intuitionistic inverse method calculus which is, in turn, a special kind of sequent calculus. It is also described how to adopt for this calculus several existing proof search strategies proposed for different logical calculi by S.Yu. Maslov, V.P. Orevkov, A.A. Voronkov, and others. In addition, a new proof search strategy is proposed that allows one to avoid redundant inferences. The paper includes results of experiments with WhaleProver on the ILTP library. We believe that Whale- Prover can be used as a test bench for different inference procedures and strategies, as well as for educational purposes.     

Mechanizing structural induction part I: Formal system

Inductive methods are basic to program proving and this paper presents the formal part of a theorem-proving system for automating mildly complex proofs by structural induction. Its features are motivated by the pragmatics of proof finding. Its syntax includes a typed language and an induction rule using a lexicographic ordering based on a substructure ordering. The domain of interpretation is a many-sorted word algebra generated by the empty set. The carriers of the algebra are ordered and functions are defined by k-recursion over them. Finally, the soundness and the weak completeness of the system are proved. The main quality of the language is its system of types and its correspondingly general induction rule.     

An Algebraic Hardware/Software Partitioning Algorithm

Hardware and software co-design is a design technique which delivers computer systems comprising hardware and software components.A critical phase of the co-design process is to decompose a program into hardware and software .This paper proposes an algebraic partitioning algorithm whose correctness is verified in program algebra.The authors inroduce a program analysis phase before program partitioning and deveop a collection of syntax-based splitting rules.The former provides the information for moving operations from software to hardware and reducing the interaction between compoents,and th latter supports a compositional approach to program partitioning.     

Deductive verification of alternating systems

Alternating systems are models of computer programs whose behavior is governed by the actions of multiple agents with, potentially, different goals. Examples include control systems, resource schedulers, security protocols, auctions and election mechanisms. Proving properties about such systems has emerged as an important new area of study in formal verification, with the development of logical frameworks such as the alternating temporal logic ATL*. Techniques for model checking ATL* over finite-state systems have been well studied, but many important systems are infinite-state and thus their verification requires, either explicitly or implicitly, some form of deductive reasoning. This paper presents a theoretical framework for the analysis of alternating infinite-state systems. It describes models of computation, of various degrees of generality, and alternating-time logics such as ATL* and its variations. It then develops a proof system that allows to prove arbitrary ATL* properties over these infinite-state models. The proof system is shown to be complete relative to validities in the weakest possible assertion language. The paper then derives auxiliary proof rules and verification diagrams techniques and applies them to security protocols, deriving a new formal proof of fairness of a multi-party contract signing protocol where the model of the protocol and of the properties contains both game-theoretic and infinite-state (parameterized) aspects.     

A matrix approach to data base exploration: Analysis of classifier results

Exploratory pattern analysis is an iterative process. In many instances, numerous iterations are required before a practical model or classification scheme can be concisely stated and adequately analyzed. There are at least three distinct functions that are required for solving the important and difficult pattern recognition problems. These are: (1) conceptualization of a classification model; (2) mathematical modeling and analyzing the practical and theoretical implications of the model; (3) testing the model on actual data. These tasks are interdependent and the investigation proceeds in what often appears to be an unsystematic approach to problem solving. This paper will address the third task and consequently, by association, hopefully affect the other two in a beneficial and constructive manner.The purpose of this article is to illustrate a general methodology, based on a matrix approach, that can be used in organizing, formatting and statistically analyzing classifier results. The discussion is intended for all individuals interested in analyzing pattern analysis and classification experiments, however, it should be of particular interest to those involved in designing interactive pattern recognition software packages. The discussion proceeds from a matrix algebra study of classifier results to techniques for statistical analysis using Cohen's kappa and Cochran's Q statistics. An example from nuclear medicine is used to illustrate the methodology.     

Integrating a formal method into a software engineering process with UML and Java

We describe how CSP-OZ, a formal method combining the process algebra CSP with the specification language Object-Z, can be integrated into an object-oriented software engineering process employing the UML as a modelling and Java as an implementation language. The benefit of this integration lies in the rigour of the formal method, which improves the precision of the constructed models and opens up the possibility of (1) verifying properties of models in the early design phases, and (2) checking adherence of implementations to models. The envisaged application area of our approach is the design of distributed reactive systems. To this end, we propose a specific UML profile for reactive systems. The profile contains facilities for modelling components, their interfaces and interconnections via synchronous/broadcast communication, and the overall architecture of a system. The integration with the formal method proceeds by generating a significant part of the CSP-OZ specification from the initially developed UML model. The formal specification is on the one hand the starting point for verifying properties of the model, for instance by using the FDR model checker. On the other hand, it is the basis for generating contracts for the final implementation. Contracts are written in the Java Modeling Language (JML) complemented by CSP_jassda, an assertion language for specifying orderings between method invocations. A set of tools for runtime checking can be used to supervise the adherence of the final Java implementation to the generated contracts. This research was partially supported by the DFG project ForMooS (grants OL 98/3-2 and WE 2290/5-1). C. B. Jones     

Hypermatrix Algebra: Theory

Algebraic manipulation of two-dimensional data structures—typical in image processing—requires operations more powerful than those afforded by classical matrix algebra. To this end, hypermatrix algebra provides a compact treatment of multidimensional objects and associated operations. Initially presented as array algebra, it uses a notation derived from tensor analysis. By extending matrix algebra with Kronecker products and matrix representations of shuffle permutations, a duality between the two algebras is shown. This serves as a means of transferring into the domain that is most convenient for a particular type of operation or representation. Hypermatrix algebra can be a powerful design tool for multidimensional massively parallel computing structures. A mathematical foundation for such an algebra is presented in this paper as a supplement to separate application notes.     

Implementing a Method for Stochastization of One-Step Processes in a Computer Algebra System

When modeling such phenomena as population dynamics, controllable flows, etc., a problem arises of adapting the existing models to a phenomenon under study. For this purpose, we propose to derive new models from the first principles by stochastization of one-step processes. Research can be represented as an iterative process that consists in obtaining a model and its further refinement. The number of such iterations can be extremely large. This work is aimed at software implementation (by means of computer algebra) of a method for stochastization of one-step processes. As a basis of the software implementation, we use the SymPy computer algebra system. Based on a developed algorithm, we derive stochastic differential equations and their interaction schemes. The operation of the program is demonstrated on the Verhulst and Lotka–Volterra models.     

形式化方法概貌

形式化方法是基于严格数学基础,对计算机硬件和软件系统进行描述、开发和验证的技术.其数学基础建立在形式语言、语义和推理证明三位一体的形式逻辑系统之上.形式化方法已经以不同程度和不同方式愈来愈多地应用在计算系统生命周期的各个阶段.介绍了形式化方法的发展历程和基本方法体系;以形式规约和形式验证为主线,综述了形式化方法的理论、方法、工具和应用的现状,展示了形式化方法与软件学科其他领域的交叉和融合;分析了形式化方法的启示,并展望了其面临的发展机遇和未来趋势.形式化方法的发展和研究现状表明：其应用已经取得了长足的进步,在提高计算系统的可靠性和安全性方面发挥了重要作用.在当今软件日益成为社会基础设施的时代,形式化方法将与人工智能、网络空间安全、量子计算、生物计算等领域和方向交叉融合,得到更加广阔的应用.研究和建立这种交叉融合的理论和方法不仅重要,而且具有挑战性.     

An Identity-Based Encryption with Equality Test scheme for healthcare social apps

It is tricky to determine whether two ciphertexts contain the same message when the messages are encrypted with different public keys. public key encryption with equality test (PKEET) addresses this problem without decryption. By integrating PKEET with identity-based encryption, identity-based encryption with equality test (IBEET) simplifies the certificate management in PKEET. In this paper, we first propose an IBEET scheme that can resist offline message recovery attacks (OMRA) and requires neither the dual-tester setting nor the group mechanism. With the help of some mathematical assumptions, we demonstrate the security of our scheme. Experiment results reveal that our scheme is efficient. From the perspective of usability, we explain why our scheme is more appropriate to be applied in healthcare social Apps than other OMRA-resistant schemes.     

The Carneades model of argument and burden of proof

We present a formal, mathematical model of argument structure and evaluation, taking seriously the procedural and dialogical aspects of argumentation. The model applies proof standards to determine the acceptability of statements on an issue-by-issue basis. The model uses different types of premises (ordinary premises, assumptions and exceptions) and information about the dialectical status of statements (stated, questioned, accepted or rejected) to allow the burden of proof to be allocated to the proponent or the respondent, as appropriate, for each premise separately. Our approach allows the burden of proof for a premise to be assigned to a different party than the one who has the burden of proving the conclusion of the argument, and also to change the burden of proof or applicable proof standard as the dialogue progresses from stage to stage. Useful for modeling legal dialogues, the burden of production and burden of persuasion can be handled separately, with a different responsible party and applicable proof standard for each. Carneades enables critical questions of argumentation schemes to be modeled as additional premises, using premise types to capture the varying effect on the burden of proof of different kinds of questions.