Synthesis of continuous-valued logic functions defined in tabular form

The choice table provides one of the techniques for the representation of functions in continuous-valued logic [1]. The need to synthesize functions from choice tables arise in the design of hybrid [2] and analog [3] computers, and also in other applications of continuous-valued logic that are surveyed in [4]. The structure of the original table is determined by the external specification of the device or unit being designed. Algorithms are available for the synthesis of continuous-valued logic functions from choice tables of a special form, for instance, from ordered choice tables [ It is noted in [ that a general algorithm to synthesize a continuous-valued logic function from an arbitrary choice table is still unknown. In the present article, we derive a criterion that decides whether a given choice table defmes some continuous-valued logic function and construct a simple algorithm to synthesize the function from the table. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 42–49, March–April, 1998.     

A second order theory of infinite trees

An axiomatic approach based on second order logic for specifying finite data types has been given in [12]. In the present paper we generalize the approach to infinite trees. Data logic CT of infinite trees is introduced and investigated. CT is based on the data logic T of finite trees. For treating infinite objects we heavily rely upon the notions of Bishop'apos;s constructive mathematics. Thus the results of the present paper are closely related with an intuitionistic type theory of infinite trees.     

An integrated system design environment: Concepts and a status report

In the construction of requirements specifications for a given problem, it is generally recommended that overspecification of the problem solution be avoided [1]. Such overspecification tends to distort the functionality required by suggesting implementation concepts at the outset. In order to avoid overspecification, and to provide a support environment to the specifier, a four-stage system design environment is proposed and has been partially implemented over a three-year period. The theoretical basis of this approach is explained in [2]. Our system-level specification language (DODAN) is developed in [3]. Based on this specification language, a prototype (DAA) [4, 5, 6] for supporting the requirements specification stage has been implemented. Our other protype (DARMS) addressing the module specification stage was developed in [7, 8]. In this paper, the current status of the project is described with an emphasis on the requirements specification stage.     

On controllability of discrete event systems in a behavioral framework

The purpose of this paper is to investigate the controllability and the achievability of discrete event systems within a behavioral framework. Based on the notion of Willems’ behavioral controllability [1, 2], we introduce a new concept related to the controllability of discrete event systems. By using the controllability proposed here and the notion related to achievable behaviors [3, 4], we show that the behavioral controllability for a given specification with respect to language is equivalent to the existence of a controller, so that an interconnected system satisfies the specification exactly. A proposed controller here is represented by the intersection of the behavior of a given plant and that of a given (controllable) specification. We also clarify that our controllers for a given specification fit the properties of well-known supervisory controllers proposed and developed by Ramadge and Wonham [5]. The text was submitted by the authors in English.     

Modular abstractions for verifying real-time distributed systems

In this work we present a verification methodology for real-time distributed systems, based on their modular decomposition into processes. Given a distributed system, each of its components is reduced by abstracting away from details that are irrelevant for the required specification. The abstract components are then composed to form an abstract system to which a model checking procedure is applied. The abstraction relation and the specification language guarantee that if the abstract system satisfies a specification, then the original system satisfies it as well.The specification languageRTL is a branching-time version of the real-time temporal logicTPTL presented in Alur and Henzinger [1]. Its model checking is linear in the size of the system and exponential in the size of the formula. Two notions of abstraction for real-time systems are introduced, each preserving a sublanguage ofRTL.     

Logical approximation for program analysis

The abstract interpretation of programs relates the exact semantics of a programming language to a finite approximation of those semantics. In this article, we describe an approach to abstract interpretation that is based in logic and logic programming. Our approach consists of faithfully representing a transition system within logic and then manipulating this initial specification to create a logical approximation of the original specification. The objective is to derive a logical approximation that can be interpreted as a terminating forward-chaining logic program; this ensures that the approximation is finite and that, furthermore, an appropriate logic programming interpreter can implement the derived approximation. We are particularly interested in the specification of the operational semantics of programming languages in ordered logic, a technique we call substructural operational semantics (SSOS). We show that manifestly sound control flow and alias analyses can be derived as logical approximations of the substructural operational semantics of relevant languages.     

Modalities for model checking: branching time logic strikes back

We consider automatic verification of finite state concurrent programs. The global state graph of such a program can be viewed as a finite (Kripke) structure, and amodel checking algorithm can be given for determining if a given structure is a model of a specification expressed in a propositional temporal logic. In this paper, we present a unified approach for efficient model checking under a broad class of generalized fairness constraints in a branching time framework extending that of Clarke et al. (1983). Our method applies to any type of fairness expressed in a certain canonical form. Almost all ‘practical’ types of fairness from the literature, including the fundamental notions of impartiality, weak fairness, and strong fairness, can be succintly written in our canonical form. Moreover, our branching time approach can easily be adapted to handle types of fairness (such as fair reachability of a predicate) which cannot even be expressed in a linear temporal logic. We go on to argue that branching time logic is always better than linear time logic for model checking. We show that given any model checking algorithm for any system of linear time logic (in particular, for the usual system of linear time logic) there is a model checking algorithm of the same order of complexity (in both the structure and formula size) for the corresponding full branching time logic which trivially subsumes the linear time logic in expressive power (in particular, for the system of full branching time logic CTL^*). We also consider an application of our work to the theory of finite automata on infinite strings.     

Passive testing and application to the GSM-MAP protocol

Passive testing is the process of collecting traces of messages exchanged between an operating implementation and its environment, in order to verify that these traces actually belong to the language accepted by the provided finite state machine specification. In this paper, we present an extension of the existing algorithms to consider an extended finite state machine as the specification. An algorithm is also introduced to take into account the number of transitions covered. These techniques are illustrated by the application to a real protocol, the GSM (global system for mobile communication)-MAP (mobile application part).     

Game-theoretic simulation checking tool

Model checking is one of the most commonly used methods for checking program correctness. In this method, one verifies a program model given by the Kripke structure (labeled transition system) rather than the program itself. The specification is usually given as a temporal logic formula. In many subtasks of model checking, it is necessary to use relations that are defined on the set of program models and preserve the satisfiability of temporal logic formulas. There exist many relations of this kind, which are called simulation relations. In the present paper, we introduce a tool designed to check a wide class of simulation relations between finite models of programs. This tool is based on the simulation checking game-theoretic approach. The tool consists of two components. The first component is the formal language, which allows one to define various simulation relations in terms of an antagonistic two-player game. The second component is a software tool that, given two labeled transition systems and simulation definition, is able to check whether this simulation is satisfied between these labeled transition systems.     

模糊交互时态逻辑的模型检测

交互时态逻辑已被广泛应用于开放系统的规范描述,交互时态逻辑的模型检测技术是一个比较重要的验证方法。为了形式化描述和验证具有模糊不确定性信息的开放系统的性质,提出了一种模糊交互时态逻辑,并讨论了它的模型检测问题。首先,引入了模糊交互时态逻辑的基于路径和基于不动点的两种语义,证明了其等价性。然后,基于其等价性,给出了模糊交互时态逻辑的模型检测算法和复杂性分析。     

Refinement of a typed WAM extension by polymorphic order-sorted types

We refine the mathematical specification of a WAM extension to typeconstraint logic programming given in [BeB96]. We provide a full specification and correctness proof of the PROTOS Abstract Machine (PAM), an extension of the WAM by polymorphic order-sorted unification as required by the logic programming language PROTOS-L, by refining the abstract type constraints used in [BeB96] to the polymorphic order-sorted types of PROTOS-L. This allows us to develop a detailed and mathematically precise account of the PAM's compiled type constraint representation and solving facilities, and to extend the correctness theorem to compilation on the fully specified PAM.The first author was partially funded by the German Ministry for Research and Technology (BMFT) in the framework of the WISPRO Project (Grant 01 IW 206). He would also like to thank the Scientific Center of IBM Germany where the work reported here was started.     

Slicing from formal semantics: Chisel—a tool for generic program slicing

We describe Chisel, a tool that synthesizes a program slicer directly from a given algebraic specification of a programming language operational semantics \(\mathcal {S}\). \(\mathcal {S}\) is assumed to be a rewriting logic specification, given in Maude, while the program is a ground term of this specification. Chisel takes \(\mathcal {S}\) and synthesizes language constructs, i.e., instructions, that produce features relevant for slicing, e.g., data dependency. We implement syntheses adjusted to each feature as model checking properties over an abstract representation of \(\mathcal {S}\). The syntheses results are used by a traditional interprocedural slicing algorithm that we parameterize by the synthesized language features. We present the tool on two language paradigms: high-level, imperative and low-level, assembly languages. Computing program slices for these languages allows for extracting traceability properties in standard compilation chains and makes our tool fitting for the validation of embedded system designs. Chisel’s slicing benchmark evaluation is based on benchmarks used in avionics.     

带数据约束的概率实时系统的验证

带数据约束的概率实时系统是指一种既带有概率时间约束又带有数据变量约束的计算系统。目前将离散数据约束和连续时间约束统一在一个概率模型中的规范及验证研究较少。提出了一种既带有连续数据约束又带有离散数据约束的规范——基于连续时间的概率ZIA规范,并给出了它的时序逻辑。对于CTL和PCTL而言,尽管这些逻辑很强大,但是只能反映时序性质,因此提出一个新的形式化语言CTML来表达度量性质查询,同时保留表达时序性质的能力并给出概率ZIA规范的验证算法。     

Analyzing partially-implemented real-time systems

Most analysis methods for real-time systems assume that all the components of the system are at roughly the same stage of development and can be expressed in a single notation, such as a specification or programming language. There are, however, many situations in which developers would benefit from tools that could analyze partially-implemented systems: those for which some components are given only as high-level specifications while others are fully implemented in a programming language. In this paper, we propose a method for analyzing such partially-implemented real-time systems. We consider real-time concurrent systems for which some components are implemented in Ada and some are partially specified using regular expressions and graphical interval logic (GIL), a real-time temporal logic. We show how to construct models of the partially-implemented systems that account for such properties as run-time overhead and scheduling of processes, yet support tractable analysis of nontrivial programs. The approach can be fully automated, and we illustrate it by analyzing a small example     

Submodule construction from concurrent system specifications

The submodule construction problem (SCP) as stated and formulated by Merlin and Bochmann [P. Merlin, G.V. Bochmann, On the construction of submodule specification and communication protocols, ACM Trans. Prog. Lang. Sys., 5(1) (1983) 1–25] is considered: given the specification of a system (module) and that of its n−1 submodules, determine the specification of the nth submodule that together with the given n−1 submodules will satisfy the given system specification. We recast SCP in a formal setting and proceed to present and prove the correctness of an algorithm for the solution of SCP where submodules are prefix-closed finite state machines.     

Programming in temporal-nonmonotonic reasoning

Nonmonotonic reasoning has been proposed as an extension to classical first-order logic. Now people are interested in temporal reasoning with nonmonotonic logic [6]. We combine the monotonic logic [7] with a temporal logic to get a more general reasoning language. We discuss a monotonic logic TML which has predicate formulas, temporal formulas and a special modal formula, and give a completeness theorem of it. We use TH() to designate the set of theorems of a temporal-nonmonotonic theory which has the same language with TML. The completeness theorem of the temporal-nonmonotonic logic naturally arises. Like the relationship between predicate logic with a practical logic programming language PROLOG, we propose a useful temporal-nonmonotonic reasoning language TN for the temporal-nonmonotonic logic. As an appendix we supply an algorithm for the programming language TN.     

采用动作时序逻辑的Web服务组合方法

基于有限状态自动机理论,将Web服务建模成一个有限状态自动机。针对网络服务描述语言(WSDL)在服务行为描述方面的缺陷对其进行扩展,提出了从扩展的WSDL到动作时序逻辑(TLA)语言的转换算法,从而可以用TLA对服务行为进行形式化描述和规范,为描述Web服务提供了一个新的方法。讨论了在动作时序逻辑中,服务组合时各组件服务的有限状态自动机的组合方式,以及伴随着服务组合,单个服务的TLA规范如何组合以形成复合服务的TLA规范的问题,并在此基础上,提出了实现TLA规范正确组合的算法思想。     

Reliable decentralized supervisory control of discrete eventsystems

We consider a discrete event system controlled by a decentralized supervisor consisting of n local supervisors, and formulate a new decentralized supervisory control problem, called a reliable decentralized supervisory control problem. A decentralized supervisor is said to be k-reliable (1相似文献