P — A logic — a compositional proof system for distributed programs

Summary This paper describes a compositional proof system called P-A logic for establishing weak total correctness and weak divergence correctness of CSP-like distributed programs with synchronous and asynchronous communication. Each process in a network is specified using logical assertions in terms of a presuppositionPre and an affirmationAff as a triple {Pre}S{Aff}. For purely sequential programs, these triples reduce to the familiar Hoare triples. In distributed programs, P-A triples allow the behaviour of a process to be specified in the context of assumptions about its communications with the other processes in the network. Safety properties of process communications, and progress properties such as finiteness and freedom from divergence can be proved. An extension of P-A logic allowing proof of deadlock freedom is outlined. Finally, proof rules for deriving some liveness properties of a program from its P-A logic specification are discussed; these properties have the form Q untilR, whereQ, R are assertions over communication traces. Other liveness properties may be derived from these properties using the rules of temporal logic. Paritosh Kulin Pandya received his Master's degree in Computer Science from the Indian Institute of Technology, Kanpur in 1982, and a Ph.D. from the Tata Institute of Fundamental Research in 1988 where he is currently employed. He has worked as a Research Officer in the Programming Research Group of the Oxford University from 1988 to 1991. Mathai Joseph has since 1985 been professor of Computer Science at the University of Warwick where he leads a group working on developing formal techniques for specifying and implementing realtime and fault-tolerant systems.Supported in part by Visiting Fellowships awarded by the Science and Engineering Research Council (research grant GR/D 90918) and the British Council     

COMPSPEN:对形状性质与数据约束进行融合推理的分离逻辑求解器

分离逻辑是经典霍尔逻辑的针对操作指针和动态数据结构的扩展,已经广泛用于对基础软件(比如操作系统内核等)的分析与验证.分离逻辑约束自动求解是提升对操作指针和动态数据结构的程序的验证的自动化程度的重要手段.针对动态数据结构的验证一般同时涉及形状性质(比如单链表、双链表、树等)和数据性质(比如有序性、数据不变性等).主要介绍能对动态数据结构的形状性质与数据约束进行融合推理的分离逻辑求解器COMPSPEN.首先介绍COMPSPEN的理论基础,包括能够同时描述线性动态数据结构的形状性质和数据约束的分离逻辑子集SLID_data、SLID_data的可满足性和蕴涵问题的判定算法.然后,介绍COMPSPEN工具的基本框架.最后,使用COMPSPEN工具进行了实例研究.收集整理了600个测试用例,在这600个测试用例上将COMPSPEN与已有的主流分离逻辑求解器Asterix、S2S、Songbird、SPEN进行了比较.实验结果表明COMPSPEN是唯一能够求解含有集合数据约束的分离逻辑求解器,而且总体来讲,能对线性数据结构上的同时含有形状性质和线性算术数据约...     

The axiomatic semantics of programs based on Hoare's logic

Summary This paper is about the Floyd-Hoare Principle which says that the semantics of a programming language can be formally specified by axioms and rules of inference for proving the correctness of programs written in the language. We study the simple language WP of while-programs and Hoare's system for partial correctness and we calculate the relational semantics of WP as this is determined by Hoare's logic. This calculation is possible by using relational semantics to build a completeness theorem for the logic. The resulting semantics AX we call the axiomatic relational semantics for WP. This AX is not the conventional semantics for WP: it need not be effectively computable or deterministic, for example. A large number of elegant properties of AX are proved and the Floyd-Hoare Principle is reconsidered.     

A symbolic framework for multi-faceted security protocol analysis

Verification of software systems, and security protocol analysis as a particular case, requires frameworks that are expressive, so as to properly capture the relevant aspects of the system and its properties, formal, so as to be provably correct, and with a computational counterpart, so as to support the (semi-) automated certification of properties. Additionally, security protocols also present hidden assumptions about the context, specific subtleties due to the nature of the problem and sources of complexity that tend to make verification incomplete. We introduce a verification framework that is expressive enough to capture a few relevant aspects of the problem, like symmetric and asymmetric cryptography and multi-session analysis, and to make assumptions explicit, e.g., the hypotheses about the initial sharing of secret keys among honest (and malicious) participants. It features a clear separation between the modeling of the protocol functioning and the properties it is expected to enforce, the former in terms of a calculus, the latter in terms of a logic. This framework is grounded on a formal theory that allows us to prove the correctness of the verification carried out within the fully fledged model. It overcomes incompleteness by performing the analysis at a symbolic level of abstraction, which, moreover, transforms into executable verification tools.     

Proof-Search in Intuitionistic Logic with Equality, or Back to Simultaneous Rigid E-Unification

We characterize provability in intuitionistic logic with equality in terms of a constraint calculus. This characterization uncovers close connections between provability in intuitionistic logic with equality and solutions to simultaneous rigid E-unification. We show that the problem of existence of a sequent proof with a given skeleton is polynomial-time equivalent to simultaneous rigid E-unifiability. This gives us a proof procedure for intuitionistic logic with equality modulo simultaneous rigid E-unification. We also show that simultaneous rigid E-unifiability is polynomial-time reducible to intuitionistic logic with equality. Thus, any proof procedure for intuitionistic logic with equality can be considered as a procedure for simultaneous rigid E-unifiability. In turn, any procedure for simultaneous rigid E-unifiability gives a procedure for establishing provability in intuitionistic logic with equality.     

Proof Search in Intuitionistic Logic with Equality, or Back to Simultaneous Rigid E-Unification

We characterize provability in intuitionistic logic with equality in terms of a constraint calculus. This characterization uncovers close connections between provability in intuitionistic logic with equality and solutions to simultaneous rigid E-unification. We show that the problem of existence of a sequent proof with a given skeleton is polynomial-time equivalent to simultaneous rigid E-unifiability. This gives us a proof procedure for intuitionistic logic with equality modulo simultaneous rigid E-unification. We also show that simultaneous rigid E-unifiability is polynomial-time reducible to intuitionistic logic with equality. Thus, any proof procedure for intuitionistic logic with equality can be considered as a procedure for simultaneous rigid E-unifiability. In turn, any procedure for simultaneous rigid E-unifiability gives a procedure for establishing provability in intuitionistic logic with equality.     

Logical foundations for representing object-oriented systems

Abstract

Object-oriented programming languages are designed for computing or simulating the behaviour of interacting objects, but their encapsulated contexts and procedural methods are not well suited to non-procedural techniques in theorem provers, optimizers, and automated design and analysis tools. Logic is the non-procedural system par excellence, but the predicate calculus notation for logic is awkward for representing and reasoning about encapsulated contexts. Conceptual graphs are a graphic system of logic that is better suited to O-O systems. First, they explicitly represent the contexts that are ignored or obscured in predicate calculus. Second, Peirce's rules of inference for reasoning with graphs are explicitly formulated in terms of contexts and the conditions for importing and exporting information from contexts. This article describes the context mechanisms of conceptual graphs, the rules of inference for reasoning with the graphs, and their use as a design language for object-oriented systems.     

Automata theory based on quantum logic: some characterizations

Automata theory based on quantum logic (abbr. l-valued automata theory) may be viewed as a logical approach of quantum computation. In this paper, we characterize some fundamental properties of l-valued automata theory, and discover that some properties of the truth-value lattices of the underlying logic are equivalent to certain properties of automata. More specifically (i) the transition relations of l-valued automata are extended to describe the transitions enabled by strings of input symbols, and particularly, these extensions depend on the distributivity of the truth-value lattices (Proposition 3.1); (ii) some properties of the l-valued successor and source operators and l-valued subautomata are demonstrated to be equivalent to a property of the truth-value lattices which is exactly equivalent to the distributive law (Proposition 4.3 and Corollary 4.4). This is a new characterization of Boolean algebras in the framework of l-valued automata theory; (iii) we verify that the intersection of two l-valued subautomata is still an l-valued subautomaton if and only if the multiplication (&) is distributive over the union in the truth-value lattices (Proposition 4.5), which is strictly weaker than the usual distributivity; (iv) we show that some topological characterizations in terms of the l-valued successor and source operators also rely on the distributivity of truth-value lattices (Theorem 5.6). Finally, we address some related topics for further study.     

Strategy logic

We introduce strategy logic, a logic that treats strategies in two-player games as explicit first-order objects. The explicit treatment of strategies allows us to specify properties of nonzero-sum games in a simple and natural way. We show that the one-alternation fragment of strategy logic is strong enough to express the existence of Nash equilibria and secure equilibria, and subsumes other logics that were introduced to reason about games, such as ATL, ATL¹, and game logic. We show that strategy logic is decidable, by constructing tree automata that recognize sets of strategies. While for the general logic, our decision procedure is nonelementary, for the simple fragment that is used above we show that the complexity is polynomial in the size of the game graph and optimal in the size of the formula (ranging from polynomial to 2EXPTIME depending on the form of the formula).     

Logical Semantics for the Rewriting Calculus

The Rewriting Calculus has been proposed as a language for defining term rewriting strategies. Rules are explicitly represented as terms, and are applied explicitly to other terms to transform them. Sets of rules may be applied to (sets of) terms non-deterministically to obtain sets of results. Strategies are implemented as rules which accept other rules as arguments and apply them in certain ways. This paper describes work in progress to strengthen the Rewriting Calculus by giving it a logical semantics. Such a semantics can provide crucial guidance for studying the language and increasing its expressive power. The latter is demonstrated by adding support to the Rewriting Calculus for what we call higher-form rewriting, where rules rewrite other rules. The logical semantics used is based on ordered linear logic. The paper develops the ideas through several examples.     

Nominal logic, a first order theory of names and binding

This paper formalises within first-order logic some common practices in computer science to do with representing and reasoning about syntactical structures involving lexically scoped binding constructs. It introduces Nominal Logic, a version of first-order many-sorted logic with equality containing primitives for renaming via name-swapping, for freshness of names, and for name-binding. Its axioms express properties of these constructs satisfied by the FM-sets model of syntax involving binding, which was recently introduced by the author and M.J. Gabbay and makes use of the Fraenkel–Mostowski permutation model of set theory. Nominal Logic serves as a vehicle for making two general points. First, name-swapping has much nicer logical properties than more general, non-bijective forms of renaming while at the same time providing a sufficient foundation for a theory of structural induction/recursion for syntax modulo α-equivalence. Secondly, it is useful for the practice of operational semantics to make explicit the equivariance property of assertions about syntax – namely that their validity is invariant under name-swapping.     

How to fully represent expert information about imprecise properties in a computer system: random sets,fuzzy sets,and beyond: an overview

To help computers make better decisions, it is desirable to describe all our knowledge in computer-understandable terms. This is easy for knowledge described in terms on numerical values: we simply store the corresponding numbers in the computer. This is also easy for knowledge about precise (well-defined) properties which are either true or false for each object: we simply store the corresponding “true” and “false” values in the computer. The challenge is how to store information about imprecise properties. In this paper, we overview different ways to fully store the expert information about imprecise properties. We show that in the simplest case, when the only source of imprecision is disagreement between different experts, a natural way to store all the expert information is to use random sets; we also show how fuzzy sets naturally appear in such random set representation. We then show how the random set representation can be extended to the general (“fuzzy”) case when, in addition to disagreements, experts are also unsure whether some objects satisfy certain properties or not.     

Modeling Combinational Circuits Using Linear Word-level Structures

In many applications of circuit design and synthesis, it is natural and in some instances essential to manipulate logic functions and model circuits using word-level representations and arithmetic operations in contrast to bit-level representations and logic operations. This paper reviews linear word-level structures and formulates their properties for combinational circuit modeling. The paper addresses the following problem: given a library of gates with their corresponding word-level representations such as linear arithmetic expressions or respective graph structures, find a word-level model of an arbitrary combinational circuit/netlist using that library of gates and minimizing memory allocation and time delay requirements. We present a comprehensive study on linearization assuming various circuit processing strategies. In particular, we develop a new approach to manipulate linear word-level representations by means of cascades. The practical applicability of linear structures and developed algorithms is strengthen by considering the problem of timing analysis. All this is supported by the experimental study on benchmark circuits.     

An improved refutation system for intuitionistic predicate logic

In this paper a refutation calculus for intuitionistic predicate logic is presented where the necessity of duplicating formulas to which rules are applied is analyzed. In line with the semantics of intuitionistic logic in terms of Kripke models a new signF _C beside the SignsT andF is added which reduces the size of the proofs and the involved nondeterminism. The resulting calculus is proved to be correct and complete. An extension of it for Kuroda logic is given.     

一类扩展的动态描述逻辑

作为描述逻辑的扩展,动态描述逻辑为语义Web服务的建模和推理提供了一种有效途径.在将语义Web服务建模为动作之后,动态描述逻辑从动作执行结果的角度提供了丰富的推理机制,但对于动作的执行过程却不能加以处理.借鉴Pratt关于命题动态逻辑的相关研究,一方面,对动态描述逻辑中动作的语义重新进行定义,将每个动作解释为由关于可能世界的序列组成的集合;另一方面,在动态描述逻辑中引入动作过程断言,用来对动作的执行过程加以刻画.在此基础上提出一类扩展的动态描述逻辑EDDL(X),其中的X表示从ALC(attributive language with complements)到SHOIN(D)等具有不同描述能力的描述逻辑.以X为描述逻辑ALCQO(attributive language with complements,qualified number restrictions and nominals)的情况为例,给出了EDDL(ALCQO)的表判定算法,并证明了算法的可终止性、可靠性和完备性.EDDL(X)可以从动作执行过程和动作执行结果两个方面对动作进行全面的刻画和推理,为语义Web服务的建模和推理提供了进一步的逻辑支持.     

Reasoning in a Restricted Temporal Logic

We consider RTL, a linear time propositional temporal logic whose only modalities are the [formula] (eventually) operator and its dual [formula] (always). Although less expressive than the full temporal logic, RTL is the fragment of temporal logic that is used most often and in many verification systems. Indeed, many properties of distributed systems discussed in the literature are RTL properties. Another advantage of RTL over the full temporal logic is in the decidability procedure; while deciding satisfiability of a formula in full temporal logic is a PSPACE complete procedure, doing so for an RTL formula is in NP. We characterize the class of ω-regular languages that are definable in RTL and show simple translations between ω-regular sets and RTL formulae that define them. We explore the applications of RTL in reasoning about communication systems. Finally, we relate variants of RTL (when interpreted over a real line segments) to several fragments of Interval Modal Logic and show that the satisfiability problem for RTL when interpreted over a real line is NP-complete.     

Exogenous Probabilistic Computation Tree Logic

We define a logic EpCTL for reasoning about the evolution of probabilistic systems. System states correspond to probability distributions over classical states and the system evolution is modelled by probabilistic Kripke structures that capture both stochastic and non–deterministic transitions. The proposed logic is a temporal enrichment of Exogenous Probabilistic Propositional Logic (EPPL). The model-checking problem for EpCTL is analysed and the logic is compared with PCTL; the semantics of the former is defined in terms of probability distributions over sets of propositional symbols, whereas the latter is designed for reasoning about distributions over paths of possible behaviour. The intended application of the logic is as a specification formalism for properties of communication protocols, and security protocols in particular; to demonstrate this, we specify relevant security properties for a classical contract signing protocol and for the so–called quantum one–time pad.     

Practical Reflection for Sequent Logics

It is well-known that adding reflective reasoning can tremendously increase the power of a proof assistant. In order for this theoretical increase of power to become accessible to users in practice, the proof assistant needs to provide a great deal of infrastructure to support reflective reasoning. In this paper we explore the problem of creating a practical implementation of such a support layer.Our implementation takes a specification of a logical theory (which is identical to how it would be specified if we were simply going to reason within this logical theory, instead of reflecting it) and automatically generates the necessary definitions, lemmas, and proofs that are needed to enable the reflected meta-reasoning in the provided theory.One of the key features of our approach is that the structure of a logic is preserved when it is reflected. In particular, all variables, including meta-variables, are preserved in the reflected representation. This also allows the preservation of proof automation—there is a structure-preserving one-to-one map from proof steps in the original logic to proof step in the reflected logic.To enable reasoning about terms with sequent context variables, we develop a principle for context induction, called teleportation.This work is fully implemented in the MetaPRL theorem prover.