基于K-模拟的抽象

尽管近年来模型检测取得了很大的进步,但是对于大系统的验证能力依然有限。在众多的状态减少和压缩技术中,抽象技术是最有效的方法之一。本文给出了基于K-模拟的抽象的高效算法,并证明了在线性时序逻辑框架下抽象的可靠性和完备性。     

Abstractions for distributed programming

The StarMod language is designed to provide its users with abstractions for distributed computations. The language is based on Wirth's definition of a “module” as impiemented in Modula. The paper discusses abstraction mechanisms for distributed access control and scheduling: in addition, several examples are used to illustrate these concepts.     

Abstractions of Random Finite-State Machines

Suppose that M is a large, complex finite-state system (fsm), and we want to construct a smaller model of it. A way of doing so, independent of any special properties that M might have, is to partition its states, inputs, and outputs into classes, collectively referred to as an abstraction. Since abstractions map many fsms into a non-deterministic machine defining an indistinguishability class, given a particular M, an optimal abstraction will minimize the size of this class. Algorithms for constructing such abstractions have been investigated in previous work.In this paper we are interested in large fsms generated by some random procedure, and want to find abstractions that minimize the expected size of an indistinguishability class. We establish various theoretical properties of abstractions optimal in an average sense, and also investigate experimentally how their characteristics change with the parameters governing the structure of the random machines.     

Abstractions for hybrid systems

We present a procedure for constructing sound finite-state discrete abstractions of hybrid systems. This procedure uses ideas from predicate abstraction to abstract the discrete dynamics and qualitative reasoning to abstract the continuous dynamics of the hybrid system. It relies on the ability to decide satisfiability of quantifier-free formulas in some theory rich enough to encode the hybrid system. We characterize the sets of predicates that can be used to create high quality abstractions and we present new approaches to discover such useful sets of predicates. Under certain assumptions, the abstraction procedure can be applied compositionally to abstract a hybrid system described as a composition of two hybrid automata. We show that the constructed abstractions are always sound, but are relatively complete only under certain assumptions.     

Abstractions in temporal information

Three prevalent abstractions in temporal information are examined by using the machinery of first order logic. The abstraction of time allows one to concentrate on temporal objects only as they relate to other temporal objects in time. It is represented by a functional relationship between temporal objects and time intervals. The abstraction of identity allows one to concentrate on how an observed phenomenon relates to other phenomena in terms of their being manifestations of the same object. It is represented by a functional relationship between temporal phenomena and “completed” temporal objects. The abstraction of circumstance embodies a focus of attention on particular configurations or states of groups of temporal phenomena. It is represented by functional relationships between thesis groups and other objects called “events” or “states”.A novel concept, called absolute/relative abstraction, is used to formalize the abstractions of time and identity. The abstraction of circumstance, on the other hand, is an example of aggregation. The significance and use of thesis abstractions in the representation and processing of historical information is discussed.     

Abstractions of data types

The use of abstraction in the context of abstract data types, is investigated. Properties to be checked are formulas in a first order logic under Kleene's 3-valued interpretation. Abstractions are defined as pairs consisting of a congruence and a predicate interpretation. Three types of abstractions are considered,∀∀, ∀∃ and ∃^0,1∀, and for each of them corresponding property preservation results are established. An abstraction refinement property is also obtained. It shows how one can pass from an existing abstraction to a (less) finer one. Finally, equationally specified abstractions in the context of equationally specified abstract data types are discussed and exemplified.On leave from the Department of Computer Science, “Al. I. Cuza” University, Iaşi 740083, RomaniaThe research reported in this paper was partially supported by the program ECO-NET 08112WJ/2004-2005 and by the National University Research Council of Romania, grants CNCSIS 632(28)/2004 and CNCSIS 632(50)/2005.     

Abstractions of Hamiltonian control systems

Given a control system and a desired property, an abstracted system is a reduced system that preserves the property of interest while ignoring modeling detail. In previous work, abstractions of linear and nonlinear control systems were considered while preserving reachability properties. In this paper, we consider the abstraction problem for Hamiltonian control systems, where, in addition to the property of interest we also preserve the Hamiltonian structure of the control system. We show how the Hamiltonian structure of control systems can be exploited to simplify the abstraction process. We then focus on local accessibility preserving abstractions, and provide conditions under which local accessibility properties of the abstracted Hamiltonian system are equivalent to the local accessibility properties of the original Hamiltonian control system.     

Efficient Abstractions for GPGPU Programming

General purpose (GP)GPU programming demands to couple highly parallel computing units with classic CPUs to obtain a high performance. Heterogenous systems lead to complex designs combining multiple paradigms and programming languages to manage each hardware architecture. In this paper, we present tools to harness GPGPU programming through the high-level OCaml programming language. We describe the SPOC library that allows to handle GPGPU subprograms (kernels) and data transfers between devices. We then present how SPOC expresses GPGPU kernel: through interoperability with common low-level extensions (from Cuda and OpenCL frameworks) but also via an embedded DSL for OCaml. Using simple benchmarks as well as a real world HPC software, we show that SPOC can offer a high performance while efficiently easing development. To allow better abstractions over tasks and data, we introduce some parallel skeletons built upon SPOC as well as composition constructs over those skeletons.     

Control Abstractions for Local Search

Comet is an object-oriented language supporting a constraint-based architecture for local search through declarative and search components. This paper proposes three novel and lightweight control abstractions for the search component, significantly enhancing the compositionality, modularity, and reuse of Comet programs. These abstractions, which includes events and checkpoints, rely on first-class closures as the enabling technology. They are especially useful for expressing, in a modular way, heuristic and meta-heuristics, unions of heterogeneous neighborhoods, and sequential composition of neighborhoods.     

Defining Database Views as Data Abstractions

The concept of data abstraction is utilized in database systems to define user interfaces via database views in database application languages and to describe the architecture of database systems. Differences between the specification and use of database views and other data abstractions realized as abstract data types are discussed. Database views are formally specified using both the algebraic specification method and the abstract model specification method. The use of database views is demonstrated via the EXT_Pascal database application language.     

Compositional Abstractions of Hybrid Control Systems

Abstraction is a natural way to hierarchically decompose the analysis and design of hybrid systems. Given a hybrid control system and some desired properties, one extracts an abstracted system while preserving the properties of interest. Abstractions of purely discrete systems is a mature area, whereas abstractions of continuous systems is a recent activity. In this paper we present a framework for abstraction that applies to discrete, continuous, and hybrid systems. We introduce a composition operator that allows to build complex hybrid systems from simpler ones and show compatibility between abstractions and this compositional operator. Besides unifying the existing methodologies we also propose constructions to obtain abstractions of hybrid control systems.     

Fortress Abstractions in X10 Framework

International Journal of Parallel Programming - Fortress provides a nice set of abstractions used widely in scientific computing. The use of such abstractions enhances the productivity of...     

Static Specification Mining Using Automata-Based Abstractions

We present a novel approach to client-side mining of temporal API specifications based on static analysis. Specifically, we present an interprocedural analysis over a combined domain that abstracts both aliasing and event sequences for individual objects. The analysis uses a new family of automata-based abstractions to represent unbounded event sequences, designed to disambiguate distinct usage patterns and merge similar usage patterns. Additionally, our approach includes an algorithm that summarizes abstract traces based on automata clusters, and effectively rules out spurious behaviors. We show experimental results mining specifications from a number of Java clients and APIs. The results indicate that effective static analysis for client-side mining requires fairly precise treatment of aliasing and abstract event sequences. Based on the results, we conclude that static client-side specification mining shows promise as a complement or alternative to dynamic approaches.     

Logic Based Abstractions of Real-Time Systems

When verifying concurrent systems described by transition systems, state explosion is one of the most serious problems. If quantitative temporal information (expressed by clock ticks) is considered, state explosion is even more serious. We present a notion of abstraction of transition systems, where the abstraction is driven by the formulae of a quantitative temporal logic, called qu-mu-calculus, defined in the paper. The abstraction is based on a notion of bisimulation equivalence, called , n-equivalence, where is a set of actions and n is a natural number. It is proved that two transition systems are , n-equivalent iff they give the same truth value to all qu-mu-calculus formulae such that the actions occurring in the modal operators are contained in , and with time constraints whose values are less than or equal to n. We present a non-standard (abstract) semantics for a timed process algebra able to produce reduced transition systems for checking formulae. The abstract semantics, parametric with respect to a set of actions and a natural number n, produces a reduced transition system , n-equivalent to the standard one. A transformational method is also defined, by means of which it is possible to syntactically transform a program into a smaller one, still preserving , n-equivalence.     

Verification of Nonconflict of Supervisors Using Abstractions

This paper presents an efficient test that uses abstractions to detect conflict in composed systems controlled by local supervisors. This test, called nonconflict test, is not applied over the languages generated by the supervisors, but over abstractions of the supervisors with some specific characteristics. The concept of observer and the definition of the set of relevant events are the basis for the approach. Two strategies to define the set of relevant events are presented, along with illustrative examples. The paper also introduces a combined strategy, which consists of applying the two strategies in sequence leading, in many cases, to better reductions than when applying each strategy independently. An example is presented to illustrate the combined strategy.      

Abstractions for Fault-Tolerant Global Computing: Extended Abstract

Global computing (WAN programming, Internet programming) distinguishes itself from local computing (LAN computing) by among other things the fact that it exposes the network to the application, rather than seeking to hide it with network transparency as in LAN programming. Global computing languages seek to provide useful abstractions for building applications in such environments. This paper introduces the pik-calculus, a calculus for asynchronous distributed programming that incorporates abstractions for building fault-tolerant global applications. The calculus incorporates notions of atomic failure and failure dependencies, from which various forms of distributed transactions and optimistic computation may be built. The pik-calculus extends the asynchronous pi-calculus with a notion of logs and “safe” operations for modifying those logs.