Speculative data-parallel algorithms for language recognition have been widely experimented for various types of finitestate automata (FA), deterministic (DFA) and nondeterministic (NFA), often derived fromregular expressions (RE). Such an algorithm cuts the input string into chunks, independently recognizes each chunk in parallel by means of identical FAs, and at last joins the chunk results and checks the overall consistency. In chunk recognition, it is necessary to speculatively start the FAs in any state, thus causing an overhead that reduces the speedup over a serial algorithm. The existing data-parallel DFA-based recognizers suffer from an excessive number of starting states, and the NFA-based ones suffer from the number of nondeterministic transitions.

This article presents a novel technique to formally verify models of real-time systems captured through a set of heterogeneous UML diagrams. The technique is based on the following key elements: (i) a subset of Unified Modeling Language (UML) diagrams, called Coretto UML (C-UML), which allows designers to describe the components of the system and their behavior through several kinds of diagrams (e.g., state machine diagrams, sequence diagrams, activity diagrams, interaction overview diagrams), and stereotypes taken from the UML Profile for Modeling and Analysis of Real-Time and Embedded Systems; (ii) a formal semantics of C-UML diagrams, defined through formulae of the metric temporal logic Tempo Reale ImplicitO (TRIO); and (iii) a tool, called Corretto, which implements the aforementioned semantics and allows users to carry out formal verification tasks on modeled systems. We validate the feasibility of our approach through a set of different case studies, taken from both the academic and the industrial domain.

We introduce bounded satisfiability checking, a verification technique that extends bounded model checking by allowing also the analysis of a descriptive model , consisting of temporal logic formulae, instead of the more customary operational model , consisting of a state transition system. We define techniques for encoding temporal logic formulae into Boolean logic that support the use of bi-infinite time domain and of metric time operators. In the framework of bounded satisfiability checking, we show how a descriptive model can be refined into an operational one, and how the correctness of such a refinement can be verified for the bounded case, setting the stage for a stepwise system development method based on a bounded model refinement. Finally, we show how the adoption of a modular approach can make the bounded refinement process more manageable and efficient. All introduced concepts are extensively applied to a set of case studies, and thoroughly experimented through Zot, our SAT solver-based verification toolset.

Many industrial systems include components interacting with each other that evolve with possibly very different speeds. To deal with this situation many formalisms adopt the abstraction of ``zero-time transitions'', which do not consume time. These, however, have several drawbacks in terms of naturalness and logic consistency, as a system is modeled to be in different states at the same time. We introduce a metric temporal logic, called X-TRIO, that uses non-standard analysis to elegantly deal with zero-time transitions in an abstract, descriptive way. We study the decidability of the logic, and we introduce a decision procedure for a subset thereof. X-TRIO has been applied in companion works to the design and verification of industrial systems.

This paper defines CLTLB(D), an extension of PLTLB (PLTL with both past and future operators) augmented with atomic formulae built over a constraint system D. The paper introduces suitable restrictions and assumptions that make the satisfiability problem decidable in many cases, although the problem is undecidable in the general case. Decidability is shown for a large class of constraint systems, and an encoding into Boolean logic is defined. This paves the way for applying existing SMT-solvers for checking the Bounded Reachability problem, as shown by various experimental results.

In bounded model checking (BMC) a system is modeled with a finite automaton and various desired properties with temporal logic formulae. Property verification is achieved by translation into boolean logic and the application of SAT-solvers. bounded satisfiability checking (BSC) adopts a similar approach, but both the system and the properties are modeled with temporal logic formulae, without an underlying operational model. Hence, BSC supports a higher-level, descriptive approach to system specification and analysis. We compare the performance of BMC and BSC over a set of case studies, using the Zot tool to translate automata and temporal logic formulae into boolean logic. We also propose a method to check whether an operational model is a correct implementation (refinement) of a temporal logic model, and assess its effectiveness on the same set of case studies. Our experimental results show the feasibility of BSC and refinement checking, with modest performance loss w.r.t. BMC.

Model checking techniques have traditionally dealt with temporal logic languages and automata interpreted over ω-words, i.e., infinite in the future but finite in the past. However, time with also an infinite past is a useful abstraction in specification. It allows one to ignore the complexity of system initialization in much the same way as system termination may be abstracted away by allowing an infinite future. One can then write specifications that are simpler and more easily understandable, because they do not include the description of the operations (such as configuration or installation) typically performed at system deployment time. The present paper is centered on the problem of satisfiability checking of linear temporal logic (LTL) formulae with past operators. We show that bounded model checking techniques can be adapted to deal with bi-infinite time in temporal logic, without incurring in any performance loss. Our claims are supported by a tool, whose application to a case study shows that satisfiability checking may be feasible also on nontrivial examples of temporal logic specifications.

We present a temporal framework suitable for the specification and verification of safety properties of real time hybrid systems. We show that, given suitable assumptions (like non-Zenoness and left continuity) continuous time can be discretized by introducing a next operator that is similar to the one usually found in discrete time temporal logics and can be safely and effectively used in specifications as well as in verification. The proofs of properties can be conducted in a deductive style, and can be easily automated, especially when they are based on induction. We validate this approach by applying it to a simple hybrid system, the well-known thermostat example

The paper "An Interval Logic for Real-Time System Specification" (Mattolini and Nesi, IEEE Trans. Software Eng., vol. 27, no. 3, pp. 208-227, Mar. 2001) presents the TILCO specification language and compares it to other existing similar languages. In this comment, we show that several of the logic formulas used for the comparison are flawed and/or overly complicated and we explain why, in this respect, the comparison is moot

The present paper reports the experience of a joint project between Politecnico di Milano and Italian State Railway FS, Infrastructure Department (became Rete Ferroviaria Italiana SpA: RFI SpA). The purpose of the project was to define procedures and rules for managing software procurement for safety-critical signalling equipment. The project covers all phases of system development, from requirements elicitation to implementation and final validation, providing requirements on methods, languages and tools to be used during software development, without any bias towards any particular technology or tool provider. The results are consistent with, and acceptable against, international standards. In particular, requirements/recommendations have been issued, tailored on various kinds of systems under examination, concerning: a) methods, techniques, languages and tools; b) organization of the provider company in terms of independence and responsibility of participating actors; c) documentation to be produced by the provider. An experimental evaluation of formal specification methods applied to signalling systems is also reported.

We advocate the need to exploit formal methods in the development of critical applications on top of RT-CORBA, a recently defined real-time extension of CORBA. We illustrate our approach using the TRIO formal notation. First, we provide a model of the core features of RT CORBA and of the real-time event service. Then we formalize the requirements of a simple application for supervision and control, and we outline the object architecture of its implementation based on the RT-CORBA platform. Finally we show how the above model (RT-CORBA and service plus application objects) can be employed in the proof that the application requirements are actually fulfilled.

We advocate the need for automated support to System Requirement Analysis in the development of time- and safety-critical computer-based systems. To this end we pursue an approach based on deductive analysis: high-level, real-world entities and notions, such as events, states, finite variability, cause-effect relations, are modeled through the temporal logic TRIO, and the resulting deductive system is implemented by means of the theorem prover PVS. Throughout the paper, the constructs and features of the deductive system are illustrated and validated by applying them to the well-known example of the Generalized Railway Crossing.

We define methods for generating execution sequences for time-critical systems based on their modularized formal specification. An execution sequence represents a behavior of a time critical system and can be used, before the final system is built, to validate the system specification against the user requirements (specification validation) and, after the final system is built, to verify whether the implementation satisfies the specification (functional testing). Our techniques generate execution sequences in the large, in that we focus on the connections among the abstract interfaces of the modules composing a modular specification. Execution sequences in the large are obtained by composing execution sequences in the small for the individual modules. We abstract from the specification languages used for the individual modules of the system, so our techniques can also be used when the modules composing the system are specified with different formalisms. We consider the cases in which connections give rise to either circular or noncircular dependencies among specification modules. We show that execution sequence generation can be carried out successfully under rather broad conditions and we define procedures for efficient construction of execution sequences. These procedures can be taken as the basis for the implementation of (semi)automated tools that provide substantial support to the activity of specification validation and functional testing for industrially-sized time critical systems.

We address the problem of increasing the impact of formal methods in the practice of industrial computer applications. We summarize the reasons why formal methods so far did not gain widespead use within the industrial environment despite several promising experiences. We suggest an evolutionary rather than revolutionary attitude in the introduction of formal methods in the practice of industrial applications, and we report on our long-standing experience which involves an academic institution. Politecnico di Milano, two main industrial partners, ENEL and CISE, and occasionally a few other industries. Our approach aims at augmenting an existing and fairly deeply rooted informal industrial methodology with our original formalism, the logic specification language TRIO. On the basis of the experiences we gained we argue that our incremental attitude toward the introduction of formal methods within the industry could be effective largely independently from the chosen formalism.

An effective means for analyzing and reasoning on software systems is to use formal specifications to simulate their execution. The simulation traces can be used for specification testing and reused, later in the development process, for functional testing of the system. It is widely acknowledged that, to deal with the complexity of industrial-size systems, specifications must be structured into modules providing abstraction mechanisms and clear interfaces. In past work (D. Mandrioloi et al., 1995), we defined and implemented a method for simulating specifications written in the TRIO temporal logic language, and applied it to functional testing of time-critical industrial systems. In this paper, we report on a tool for analyzing TRIO specifications taking advantage of their modular structure, overcoming the well-known state-explosion problem and making the proposed method really scalable. We discuss the fundamental operations and the algorithms on which the tool is based. Then we illustrate its use in a realistic case study inspired by an industrial application. Finally, we comment on the overall results in terms of the usability of the tool and the effectiveness of the approach, and we suggest some future improvements.

We address the problem of generating functional test cases for complex, highly structured time-critical systems starting from a modularized logic-based specification written in the TRIOR+ language, an object-oriented extension of the temporal logic TRIO.First, we present methods for producing test cases for a TRIO+ specification module, referring both to the internal, hidden, portion of the module and to its interface. Then, we discuss criteria to be used in the construction of test cases from a TRIO+ specification based on its composing modules and the connections among their interfaces. We formally define the notions related to test case derivation from TRIO+ modules and we introduce an executable language for describing a variety of strategies for constructing test cases for structured TRIO+ specifications starting from (parts of) the test cases of the composing modules. This language can be the basis for the implementation of an interactive tool for the semiautomatic construction of functional test cases from complex time-critical systems starting from their TRIO+ specification.

We address the problem of automated derivation of functional test cases for real-time systems, by introducing techniques for generating test cases from formal specifications written in TRIO, a language that extends classical temporal logic to deal explicitly with time measures. We describe an interactive tool that has been built to implement these techniques, based on interpretation algorithms of the TRIO language. Several heuristic criteria are suggested to reduce drastically the size of the test cases that are generated. Experience in the use of the tool on real-life cases is reported.

We emphasize the importance of formal executable specifications in the development of real-time systems, as a means to assess the adequacy of the requirements before a costly development process takes place. TRIO is a first-order temporal logic language for executable specification of real-time systems that deals with time in a quantitative way by providing a metric to indicate distance in time between events and length of time intervals. We summarize the language and its model-parametric semantics. Then we present an algorithm to perform history checking, i.e., to check that a history of the system satisfies the specification. This algorithm can be used as a basis for an effective specification testing tool. The algorithm is described; an estimation of its complexity is provided; and the main functionalities of the tool are presented, together with sample test cases. Finally, we draw conclusions and indicate directions of future research.

We define TRIO + , an object-oriented logical language for modular system specification. TRIO + is based on TRIO, a first-order temporal language that is well suited to the specification of embedded and real-time systems, and that provides an effective support to a variety of validation activities, like specification testing, simulation, and property proof. Unfortunately, TRIO lacks the ability to construct specifications of complex systems in a systematic and modular way. TRIO + combines the use of constructs for hierarchical system decomposition and object-oriented concepts like inheritance and genericity with an expressive and intuitive graphic notation, yielding a specification language that is formal and rigorous, yet still flexible, readable, general, and easily adaptable to the user's needs. After introducing and motivating the main features of the language, we illustrate its application to a nontrivial case study extracted from a real-life industrial application.

Addresses the problem of formally analyzing the properties of real-time systems. We propose a method based on modeling the system as a timed Petri net and on specifying its properties in TRIO, an extension of temporal logic suitable for dealing explicitly with time and for measuring it. Timed Petri nets are axiomatized in terms of TRIO, so that their properties can be derived as theorems in the same spirit as the classical Hoare method allows one to prove properties of programs coded in a Pascal-like language. The method is also illustrated through an example.>

Process modeling is a rather young and very active research area. During the last few years, new languages and methods have been proposed to describe software processes. In this paper we try to clarify the issues involved in software process modeling and identify the main approaches. We start by motivating the use of process modeling and its main objectives. We then propose a list of desirable features for process languages. The features are grouped as either already provided by languages from other fields or as specific features of the process domain. Finally, we review the main existing approaches and propose a classification scheme.

Abstract Specifications of information systems applications are often based on the use of entity‐relationship (ER) and data‐flow diagrams (DFD), which cover, respectively, the conceptual modelling of data and funtions. This paper introduces VLP: an executable visual language for formal specifications and prototyping which integrates ER and DFD diagrams in a semantically rigorous and clear way. Unlike existing commercial products (so‐called CASE tools), which can support good‐quality documentation, simple forms of consistency checking and bookkeeping, VLP also supports executable specifications, which provide a prototype of the desired application. After reviewing the principles of VLP, the paper outlines the structure of the ECASET environment in which VLP is embedded. In particular, it shows how the environment supports the stepwise derivation of specifications, from informal to formal, and how it supports specification‐in‐the‐large.

We emphasize the importance of formal executable specifications in the development of real-time systems, as a means to assess the adequacy of the requirements before a costly development process takes place.TRIO is a first order temporal logic language for executable specification of real-time systems that deals with time in a quantitative way by providing a metric to indicate distance in time between events and length of time intervals.We summarise the language, its straightforward model-theoretic semantics, and a tableaux-based algorithm to decide satisfiability.Then we present an efficient algorithm to perform history-checking, i.e., to check that a history of the system satisfies the specification.This algorithm can be used as a basis for an effective specification testing tool.The algorithm is described, a qualitative estimation of its complexity is provided, and the main functionalities of the tool are presented, together with sample test cases.Finally, we draw the conclusions and indicate directions of future research.

Process modeling is an active research area. During the last few years, new languages and methods have been proposed to describe software processes. In this paper, the authors clarify the issues involved in software process modeling and identify the main approaches. They also review the main existing approaches and propose a classification scheme.>

TRIO is a formal notation for the logic-based specification of real-time systems. In this paper the language and its straightforward model-theoretic semantics are briefly summarized. Then the need for assigning a consistent meaning to TRIO specifications is discussed, with reference to a variety of underlying time structures such as infinite-time structures (both dense and discrete) and finite-time structures. The main motivation is the ability to validate formal specifications. A solution to this problem is presented, which gives a new, model-parametric semantics to the language. An algorithm for constructively verifying the satisfiability of formulas in the decidable cases is defined, and several important temporal properties of specifications are characterized.