Search

In computer science, functional orbits – i.e., tracks left by the iterations of a function – in a finite domain naturally appear at a high or a low level. This paper introduces a Coq logical orbit framework, the purpose of which is to help rigorously developing software systems with some complex data structures from specification to implementation. The result is a Coq library of orbit concepts formalized as definitions, lemmas and theorems. Most of them are inspired by our previous work in geometric modelling, where combinatorial hypermaps were used to describe surface subdivisions appearing in computational geometry problems, e.g., building convex hulls or Delaunay diagrams. Now, this domain remains a reference for us, but our results are drastically extended and usable in other computer science areas. The proof of Floyd's cycle-detection algorithm, known as “the tortoise and the hare”, confirms that point. The library contains operations to observe, traverse and update orbits – addition, deletion, mutation, transposition – with proofs of their behavior. It focuses on the important case where the involved function is a partial injection. In this case, it defines a connectivity relationship and evaluates the variation of the number of connected components during updates. [ABSTRACT FROM AUTHOR]

Formal specification is an active research field in software engineering of this century, where different configurations and techniques are employed and although their industrial use is still limited, the scientific community currently has a different understanding about its usefulness and necessity. Until present time, researchers' work focuses on the specification written during the design of the preliminary functional model, for this reason it mainly focuses on evaluating the related tools. In this paper, a literature review is performed, covering the essence, function, use and disadvantages of formal specification techniques and some assessment and evaluation criteria are analyzed regarding their weaknesses. The results become the basis for future work formulation, aimed to the strengthening of formal specification as a core research activity. [ABSTRACT FROM AUTHOR]

We address the problem of practical manipulation planning for rearrangement tasks of many movable objects. We study a special case of the rearrangement task, where the only allowed manipulation is pushing. We search for algorithms that can provide practical planning time for most common scenarios. We present a hierarchical classification of manipulation problems into several classes, each characterized by properties of the plans that can solve it. Such a classification allows one to consider each class individually, to analyze and exploit properties of each class, and to suggest individual planning methods accordingly. Following this classification, we suggest algorithms for two of the defined classes. Both items have been tested in a simulated environment, with up to 32 movable objects and 66 combined DOF. We present the simulations results as well as some experimental results using a real platform. [ABSTRACT FROM PUBLISHER]

In this paper, we demonstrate how model checking can be used to verify safety properties for event-driven systems. SCR tabular requirements describe required system behavior in a format that is intuitive, easy to read, and scalable to large systems (e.g., the software requirements for the A7 aircraft). Model checking of temporal logics has been established as a sound technique for verifying properties of hardware systems. We have developed an automated technique for formalizing the semiformal SCR requirements and for transforming the resultant formal specification onto a finite structure that a model checker can analyze. This technique was effective in uncovering violations of system invariants in both an automobile cruise control system and a water-level monitoring system. [ABSTRACT FROM AUTHOR]

This paper describes the Penelope verification editor and its formal basis. Penelope is a prototype system for the interactive development and verification of programs that are written in a rich sub- set of sequential Ada. Because it generates verification conditions incrementally, Penelope can be used to develop a program and its correctness proof in concert. If an already-verified program is modified, one can attempt to prove the modified version by replaying and modifying the original sequence of proof steps. Verification conditions are generated by predicate transformers whose logical soundness can be proven by establishing a precise formal connection between predicate transformation and denotational definitions in the style of continuation semantics. Penelope's specification language, Larch/Ada, belongs to the family of Larch interface languages. It scales up properly, in the sense that we can demonstrate the soundness of decomposing an implementation hierarchically and reasoning locally about the implementation of each node in the hierarchy. [ABSTRACT FROM AUTHOR]

An important principle of building trustworthy systems is to rigorously analyze the critical requirements early in the development process, even before starting system design. Existing proof methods for systems of communicating processes focus on the bottom-up composition of component-level specifications into system-level specifications. Trustworthy system development requires, instead, the top-down derivation of component requirements from the critical system requirements. This paper describes a formal method for decomposing the requirements of a system into requirements of its component processes and a minimal, possibly empty, set of synchronization requirements. The Trace Model of Hoare's Communicating Sequential Processes (CSP) is the basis for the formal method. We apply the method to an abstract voice transmitter and describe the role that the EHDM verification system plays in the transmitter's decomposition. In combination with other verification techniques, we expect that the method defined here will promote the development of more trustworthy systems. [ABSTRACT FROM AUTHOR]

Formal program construction by transformations is a method of software development in which a program is derived from a formal problem specification by manageable, controlled transformation steps which guarantee that the final product meets the initial specification. This methodology has been investigated in the Munich project CIP (computer-aided, intuition-guided programming). The research includes the design of a wide-spectrum language specifically tailored to the needs of transformational programming, the construction of a transformation system to support the methodology, and the study of transformation rules and other methodological issues. Particular emphasis has been laid on developing a sound theoretical basis for the overall approach. [ABSTRACT FROM AUTHOR]

In the paper [1], Theorem 23 and Example 24 are incorrect. The corrected version is presented in this note. [ABSTRACT FROM AUTHOR]