Dynamic temporal interpretation contexts for temporal abstraction

Temporal abstraction is the task of abstracting higher‐level concepts from time‐stamped data in a context‐sensitive manner. We have developed and implemented a formal knowledge‐based framework for decomposing and solving that task that supports acquisition, maintenance, reuse, and sharing of temporal‐abstraction knowledge. We present the logical model underlying the representation and runtime formation of interpretation contexts. Interpretation contexts are relevant for abstraction of time‐oriented data and are induced by input data, concluded abstractions, external events, goals of the temporal‐abstraction process, and certain combinations of interpretation contexts. Knowledge about interpretation contexts is represented as a context ontology and as a dynamic induction relation over interpretation contexts and other proposition types. Induced interpretation contexts are either basic, composite, generalized, or nonconvex. We provide two examples of applying our model using an implemented system; one in the domain of clinical medicine (monitoring of diabetes patients) and one in the domain of traffic engineering (evaluation of traffic‐control actions). We discuss several distinct advantages to the explicit separation of interpretation‐context propositions from the propositions inducing them and from the abstractions created within them. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Interpreting Abstract Interpretations in Membership Equational Logic

We present a logical framework in which abstract interpretations can be naturally specified and then verified. Our approach is based on membership equational logic which extends equational logics by membership axioms, asserting that a term has a certain sort. We represent an abstract interpretation as a membership equational logic specification, usually as an overloaded order-sorted signature with membership axioms. It turns out that, for any term, its least sort over this specification corresponds to its most concrete abstract value. Maude implements membership equational logic and provides mechanisms to calculate the least sort of a term efficiently. We first show how Maude can be used to get prototyping of abstract interpretations “for free.” Building on the meta-logic facilities of Maude, we further develop a tool that automatically checks an abstract interpretation against a set of user-defined properties. This can be used to select an appropriate abstract interpretation, to characterize the specific loss of information during abstraction, and to compare different abstractions with each other.     

Designing and modeling cyberworlds using the incrementally modular abstraction hierarchy based on homotopy theory

For designing and modeling complicated and sophisticated systems such as cyberworlds, their mathematical foundation is critical. To realize it, two important properties called the homotopy lifting property (HLP) and homotopy extension property (HEP) are applied for designing and modeling a system in a bottom-up way and a top-down way, respectively. In this paper, an enterprise system and a real-time embedded system are considered as important socially emerging cases of cyberworlds, where the π-calculus processes for describing these behaviors formally, a Petri net for explaining process interactions, and XMOS XC programs are modeled and designed by our approach. The spaces in both properties are specified by the incrementally modular abstraction hierarchy by climbing down the abstraction hierarchy from the most abstract homotopy level to the most specific view level, while keeping invariants such as homotopy equivalence and topological equivalence.     

On using data abstractions for model checking refinements

In this paper we investigate how standard model checkers can be applied to checking refinement relationships between Z specifications. The major obstacle to such a use are the (potentially) infinite data domains in specifications. Consequently, we examine the application of data abstraction techniques for reducing the infinite to a finite state space. Since data abstractions do, however, decrease the amount of information in a specification, refinement can—in general—not be proven on the abstractions anymore, it can only be disproved. The model checker can thus be used to generate counter examples to a refinement relationship. Here, we show how abstract specifications can be systematically constructed (from a given data abstraction) and how a standard model checker (FDR) can be applied to find counter examples in case when refinement is absent. We especially discuss the applicability of the construction method: it constructs abstract specifications which are either upward or downward simulations of the original specifications, and depending on the operations in the specification and the data abstraction chosen, such a construction might succeed or fail. The construction abstracts both the input/output as well as the state.     

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.     

Abstraction as a means for end-user computing in creative applications

End-user computing is needed in creative artistic applications or integrated editing environments, where the activity cannot be planned in advance. Following the paper by Orlarey et al., concrete abstractions (abstractions from examples) are suggested as a new mode for function definition, appropriate for end-user editor programmability. For certain applications, the direct, associative, not planned in advance character of concrete abstraction plays a qualitative role in the mere ability to specify abstractions. In this paper, we propose to use concrete abstraction as a general tool for end-user programmability in editors. We distinguish two kinds of abstractions: value abstraction and structure abstraction, and explain how they can be combined. We describe a framework of historical editing that is based on a double view, in which the two abstraction kinds are combined. Finally, BOOMS, an implemented prototype for such an editing framework, is described. BOOMS is a domain-independent toolkit, with three sample instantiations. We believe that the proposed framework captures the conceptualization operation that characterizes creative, associative work types and addresses the needs for end-user computing in integrated environments.     

Abstraction-guided synthesis of synchronization

We present a novel framework for automatic inference of efficient synchronization in concurrent programs, a task known to be difficult and error-prone when done manually. Our framework is based on abstract interpretation and can infer synchronization for infinite state programs. Given a program, a specification, and an abstraction, we infer synchronization that avoids all (abstract) interleavings that may violate the specification, but permits as many valid interleavings as possible. Combined with abstraction refinement, our framework can be viewed as a new approach for verification where both the program and the abstraction can be modified on-the-fly during the verification process. The ability to modify the program, and not only the abstraction, allows us to remove program interleavings not only when they are known to be invalid, but also when they cannot be verified using the given abstraction. We implemented a prototype of our approach using numerical abstractions and applied it to verify several example programs.     

π-RED*—A graph reducer for a full-fledged γ-calculus

This paper describes an applicative order graph reducer which under interactive control performs high-level program transformations that are governed by the reduction semantics of a full-fledged untyped γ-calculus. To do so with competitive speed, high-level functional programs are by a pre-processor reversibly converted into graph representations of γ-terms. Its subterms are closed by the abstraction of relatively free variables only to the extent absolutely necessary to avoid the complexity of full β-reductions at run-time. Processing these γ-terms is based on high-level interpretation which exploits the simplicity and efficiency of naive graph pointer substitutions when reducing function calls. Partially or completely reduced graphs are by a post-processor re-converted into high-level programs. Full β-reductions are only employed by the pre- and post-processor to maintain correct binding levels when abstracting free variables from γ-terms and when undoing these abstractions or reducing partial applications left over as closures, respectively.     

A Specification Method for Specifying Data and Procedural Abstractions

A specifilcation method designed primarily for specifying data abstractions, but suitable for specifying procedural abstractions as well, is described. The specification method is based on the abstract model approach to specifying abstractions. Several data abstractions and procedural abstractions are specified and a proof of implementation correctness is given for one of the data abstractions–a symbol table.     

Symbolic execution with abstraction

We address the problem of error detection for programs that take recursive data structures and arrays as input. Previously we proposed a combination of symbolic execution and model checking for the analysis of such programs: we put a bound on the size of the program inputs and/or the search depth of the model checker to limit the search state space. Here we look beyond bounded model checking and consider state matching techniques to limit the state space. We describe a method for examining whether a symbolic state that arises during symbolic execution is subsumed by another symbolic state. Since the number of symbolic states may be infinite, subsumption is not enough to ensure termination. Therefore, we also consider abstraction techniques for computing and storing abstract states during symbolic execution. Subsumption checking determines whether an abstract state is being revisited, in which case the model checker backtracks—this enables analysis of an under-approximation of the program behaviors. We illustrate the technique with abstractions for lists and arrays. We also discuss abstractions for more general data structures. The abstractions encode both the shape of the program heap and the constraints on numeric data. We have implemented the techniques in the Java PathFinder tool and we show their effectiveness on Java programs. This paper is an extended version of Anand et al. (Proceedings of SPIN, pp. 163–181, 2006).     

Verifying Time Partitioning in the DEOS Scheduling Kernel

This paper describes an experiment to use the Spin model checking system to support automated verification of time partitioning in the Honeywell DEOS real-time scheduling kernel. The goal of the experiment was to investigate whether model checking with minimal abstraction could be used to find a subtle implementation error that was originally discovered and fixed during the standard formal review process. The experiment involved translating a core slice of the DEOS scheduling kernel from C++ into Promela, constructing an abstract “test-driver” environment and carefully introducing several abstractions into the system to support verification. Attempted verification of several properties related to time-partitioning led to the rediscovery of the known error in the implementation. The case study indicated several limitations in existing tools to support model checking of software. The most difficult task in the original DEOS experiment was constructing an adequate environment to close the system for verification. The fidelity of the environment was of crucial importance for achieving meaningful results during model checking. In this paper, we describe the initial environment modeling effort and a follow-on experiment with using semi-automated environment generation methods. Program abstraction techniques were also critical for enabling verification of DEOS. We describe an implementation scheme for predicate abstraction, an approach based on abstract interpretation, which was developed to support DEOS verification.     

The SH-Verification Tool — Abstraction-Based Verification of Co-operating Systems

The sh-verification tool comprises computing abstractions of finite-state behaviour representations as well as automata and temporal logic based verification approaches. To be suitable for the verification of so called co-operating systems, a modified type of satisfaction relation (approximate satisfaction) is considered. Regarding abstraction, alphabetic language homomorphisms are used to compute abstract behaviours. To avoid loss of important information when moving to the abstract level, abstracting homomorphisms have to satisfy a certain property called simplicity on the concrete (i.e. not abstracted) behaviour. The well known state space explosion problem is tackled by a compositional method combined with a partial order method. Received March 1997 / Accepted in revised form July 1998     

Scope Dominance with Upward Monotone Quantifiers

We give a complete characterization of the class of upward monotone generalized quantifiers Q₁ and Q₂ over countable domains that satisfy the scheme Q₁ x Q₂ y φ → Q₂ y Q₁ x φ. This generalizes the characterization of such quantifiers over finite domains, according to which the scheme holds iff Q₁ is ∃ or Q₂ is ∀ (excluding trivial cases). Our result shows that in infinite domains, there are more general types of quantifiers that support these entailments.     

Abstract Graph Transformation

Graphs may be used as representations of system states in operational semantics and model checking; in the latter context, they are being investigated as an alternative to bit vectors. The corresponding transitions are obtained as derivations from graph production rules.In this paper we propose an abstraction technique in this framework: the state graphs are contracted by collecting nodes that are sufficiently similar (resulting in smaller states and a finite state space) and the application of the graph production rules is lifted to this abstract level. Since graph abstractions and rule applications can all be computed completely automatically, we believe that this can be the core of a practically feasible technique for software model checking.     

On the calculus of positively constructed formulas for automated theorem proving

The paper deals with an expressive logic language LF and its calculus. Formulas of this language consist of some large-scale structural elements, such as type quantifiers. The language LF contains only two logic symbols—∀ and ∃, which form the set of logic connectives of the language. The logic calculus JF and complete strategy for automated proof search based on a single unary rule of inference are considered. This calculus has a number of other features which lead to the reduction of the combinatorial complexity of finding the deductions in comparison to the known systems for automated theorem proving as the Resolution method and Genzen calculus. Problems of effective implementation of JF as a program system for automated theorem proving are considered.     

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.