Deterministic parsing of tree-structured data is usually performed sequentially left-to-right. Recently however, also motivated by the need to process extremely large data sets, a parallel version thereof has been devised which, thanks to the theoretical features of operator precedence languages (OPL) particularly well-suited to split the input into separate chunks, provided high improvements w.r.t. traditional sequential parsing. Further investigation pointed out a restriction imposed on the OPL formalism that prevents from fully exploiting parallelism and proposed an improvement of the original algorithm which proved effective in many practical cases. Stimulated by the above contribution here we remove the mentioned restriction on OPL and build a new parallel parser generator based thereon. We conducted a comparative experimentation among the three parallel algorithms that showed a consistent further improvement w.r.t. both the previous ones (with an exception in the case of purely sequential execution). Based on these early results, we believe that the horizon of parallel parsing large tree-structured data promises dramatic gains of efficiency in the analysis of this fundamental data structure.

Operator precedence languages (OPLs) enjoy the local parsability property, which means that a code fragment enclosed within a pair of markers playing the role of parentheses can be parsed with no knowledge of its external context. This property has been exploited to build parallel parsers for languages formalized as OPLs. It has been observed, however, that when the syntax trees of sentences have a linear substructure, parsing must necessarily proceed sequentially, making it ineffective to split such a subtree into chunks to be processed in parallel. This inconvenience derives from the hypothesis that the equality precedence relation cannot be cyclic, which has been so far assumed by most literature on OPLs. This hypothesis was motivated by the need to keep the mathematical notation as simple as possible, although it caused a discrepancy between the expressive power of operator precedence grammars and other formalisms defining OPLs such as operator precedence automata, monadic second order logic and operator precedence expressions, which do not assume acyclicity. We present an enriched version of operator precedence grammars, called cyclic , that allows for a simplified version of regular expressions in the right hand sides of grammar rules. For this class of operator precedence grammars the acyclicity hypothesis of the equality precedence relation is no more needed to guarantee the algebraic properties of the generated languages. The expressive power of the cyclic grammars is now fully equivalent to that of other formalisms defining OPLs. As a result, cyclic operator precedence grammars produce unranked syntax trees and sentences with flat unbounded substructures that can be naturally partitioned into chunks suitable for parallel parsing.

A classic result in formal language theory is the equivalence among non-counting, or aperiodic, regular languages, and languages defined through star-free regular expressions, or first-order logic. Past attempts to extend this result beyond the realm of regular languages have met with difficulties: for instance it is known that star-free tree languages may violate the non-counting property and there are aperiodic tree languages that cannot be defined through first-order logic. We extend such classic equivalence results to a significant family of deterministic context-free languages, the operator-precedence languages (OPL), which strictly includes the widely investigated visibly pushdown, alias input-driven, family and other structured context-free languages. The OP model originated in the '60s for defining programming languages and is still used by high performance compilers; its rich algebraic properties have been investigated initially in connection with grammar learning and recently completed with further closure properties and with monadic second order logic definition. We introduce an extension of regular expressions, the OP-expressions (OPE) which define the OPLs and, under the star-free hypothesis, define first-order definable and non-counting OPLs. Then, we prove, through a fairly articulated grammar transformation, that aperiodic OPLs are first-order definable. Thus, the classic equivalence of star-freeness, aperiodicity, and first-order definability is established for the large and powerful class of OPLs. We argue that the same approach can be exploited to obtain analogous results for visibly pushdown languages too.

The problem of extending model checking from finite state machines to procedural programs has fostered much research toward the definition of temporal logics for reasoning on context-free structures. The most notable of such results are temporal logics on Nested Words, such as CaRet and NWTL. Recently, Precedence Oriented Temporal Logic (POTL) has been introduced to specify and prove properties of programs coded trough an Operator Precedence Language (OPL). POTL is complete w.r.t. the FO restriction of the MSO logic previously defined as a logic fully equivalent to OPL. POTL increases NWTL’s expressive power in a perfectly parallel way as OPLs are more powerful that nested words. In this article, we produce a model checker, named POMC, for OPL programs to prove properties expressed in POTL. To the best of our knowledge, POMC is the first implemented and openly available model checker for proving tree-structured properties of recursive procedural programs. We also report on the experimental evaluation we performed on POMC on a nontrivial benchmark.

The problem of model checking procedural programs has fostered much research towards the definition of temporal logics for reasoning on context-free structures. The most notable of such results are temporal logics on Nested Words, such as CaRet and NWTL. Recently, the logic OPTL was introduced, based on the class of Operator Precedence Languages (OPLs), more powerful than Nested Words. We define the new OPL-based logic POTL and prove its FO-completeness. POTL improves on NWTL by enabling the formulation of requirements involving pre/post-conditions, stack inspection, and others in the presence of exception-like constructs. It improves on OPTL too, which instead we show not to be FO-complete; it also allows to express more easily stack inspection and function-local properties. In a companion paper we report a model checking procedure for POTL and experimental results based on a prototype tool developed therefor. For completeness a short summary of this complementary result is provided in this paper too.

Abstract The problem of model checking procedural programs has fostered much research towards the definition of temporal logics for reasoning on context-free structures. The most notable of such results are temporal logics on Nested Words, such as CaRet and NWTL. Recently, the logic OPTL was introduced, based on the class of Operator Precedence Languages (OPL), more powerful than Nested Words. We define the new OPL-based logic POTL, and provide a model checking procedure for it. POTL improves on NWTL by enabling the formulation of requirements involving pre/post-conditions, stack inspection, and others in the presence of exception-like constructs. It improves on OPTL by being FO-complete, and by expressing more easily stack inspection and function-local properties. We developed a model checking tool for POTL, which we experimentally evaluate on some interesting use-cases.

A crucial aspect of physical human-robot collaboration (HRC) is to maintain a safe common workspace for human operator. However, close proximity between human-robot and unpredictability of human behavior raises serious challenges in terms of safety. This article proposes a risk analysis methodology for collaborative robotic applications, which is compatible with well-known standards in the area and relies on formal verification techniques to automate the traditional risk analysis methods. In particular, the methodology relies on temporal logic-based models to describe the different possible ways in which tasks can be carried out, and on fully automated formal verification techniques to explore the corresponding state space to detect and modify the hazardous situations at early stages of system design.

In the last years renewed investigation of operator precedence languages (OPL) led to discover important properties thereof: OPL are closed with respect to all major operations, are characterized, besides the original grammar family, in terms of an automata family (OPA) and an MSO logic; furthermore they significantly generalize the well-known visibly pushdown languages (VPL). In another area of research, quantitative models of systems are also greatly in demand. In this paper, we lay the foundation to marry these two research fields. We introduce weighted operator precedence automata and show how they are both strict extensions of OPA and weighted visibly pushdown automata. We prove a Nivat-like result which shows that quantitative OPL can be described by unweighted OPA and very particular weighted OPA. In a Büchi-like theorem, we show that weighted OPA are expressively equivalent to a weighted MSO-logic for OPL.

Operator precedence languages were introduced half a century ago by Robert Floyd to support deterministic and efficient parsing of context-free languages. Recently, we renewed our interest in this class of languages thanks to a few distinguishing properties that make them attractive for exploiting various modern technologies. Precisely, their local parsability enables parallel and incremental parsing, whereas their closure properties make them amenable to automatic verification techniques, including model checking. In this paper we provide a fairly complete theory of this class of languages: we introduce a class of automata with the same recognizing power as the generative power of their grammars; we provide a characterization of their sentences in terms of monadic second-order logic as has been done in previous literature for more restricted language classes such as regular, parenthesis, and input-driven ones; we investigate preserved and lost properties when extending the language sentences from finite length to infinite length ($\omega$-languages). As a result, we obtain a class of languages that enjoys many of the nice properties of regular languages (closure and decidability properties, logic characterization) but is considerably larger than other families---typically parenthesis and input-driven ones---with the same properties, covering “almost” all deterministic languages.

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.

In this paper we argue that the modeling activity in the development of software-intensive systems should formalize as much as possible of the environment in which the application being developed operates. We also show that a rich formal model of the environment helps developers clearly state requirements that might typically be considered intrinsically informal (or non- formalizable in general). To illustrate this point, we show how a requirement for "orderly safe traffic" in a traffic system can be modeled, and we briefly discuss the benefits thereof.

We discuss the technical skills that a software engineer should possess. We take the viewpoint of a school of engineering and put the software engineer's education in the wider context of engineering education. We stress both the common aspects that crosscut all engineering fields and the specific issues that pertain to software engineering. We believe that even in a continuously evolving field like software, education should provide strong and stable foundations based on mathematics and science, emphasize the engineering principles, and recognize the stable and long-lasting design concepts. Even though the more mundane technological solutions cannot be ignored, the students should be equipped with skills that allow them to understand and dominate the evolution of technology.

We introduce a formal model for describing Real-Time CORBA-based applications, and a set of guidelines to formally check that the design of such an application is consistent with its specification. The model and the guidelines are then applied to the verification of a simple test application.

The design of distributed applications in a CORBA-based environment can be carried out by means of an incremental approach, which starts from the specification and leads to the high-level architectural design. This article discusses a methodology to transform a formal specification written in TRIO into a high-level design document written in an extension of TRIO, named TRIO/CORBA (TC). The TC language is suited to formally describe the high-level architecture of a CORBA-based application. As a result, designers are offered high-level concepts that precisely define the architectural elements of an application. Furthermore, TC offers mechanisms to extend its base semantics, and can be adapted to future developments and enhancements in the CORBA standard. The methodology and the associated language are presented through a case study derived from a real Supervision and Control System.

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.

The design of distributed applications in a CORBA based environment can be carried out by means of an incremental approach, which starts from the specification and leads to the high level architectural design. This is done by introducing in the specification all typical elements of CORBA and by providing a methodological support to the designers. The paper discusses a methodology to transform a formal specification written in TRIO into a high level design document written using an extension of TRIO named TC. The TC language is suited to formally describe the high level architecture of a CORBA based application. The methodology and the associated language are presented by means of an example involving a real Supervision and Control System.

We report on our experience in the Esprit OpenDREAMS project that targets the domain of Supervision and Control Systems (SCS). During this project we studied how a CORBA-based application can be designed starting from a typical SCS requirement document by integrating a formal approach with some CORBA concepts. We present a case study that shows how an existing object-oriented methodology based on the formal specification language TRIO can be tailored towards supporting CORBA-based applications. The application taken into account is in the field of the Energy Management Systems, namely a diagnostic system for the steam condenser of a thermoelectric power plant. The paper describes how to obtain the architectural design of a CORBA-based application starting from the formal specification of its requirements expressed in TRIO by means of a sequence of transformation steps. At the end of such sequence of steps a complete structure of the application classes, with their mutual relations and their IDL interfaces, is built. Finally, the paper discusses how TRIO can be used to validate the architectural choices made with respect to the application critical requirements. Copyright © 2000 John Wiley & Sons, Ltd.

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.

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.

ASTRAL is a formal specification language for real-time systems. It is intended to support formal software development, and therefore has been formally defined. This paper focuses on how to formally prove the mathematical correctness of ASTRAL specifications. ASTRAL is provided with structuring mechanisms that allow one to build modularized specifications of complex systems with layering. In this paper, further details of the ASTRAL environment components and the critical requirements components, which were not fully developed in previous papers, are presented. Formal proofs in ASTRAL can be divided into two categories: interlevel proofs and intralevel proofs. The former deal with proving that the specification of level i+1 is consistent with the specification of level i, and the latter deal with proving that the specification of level i is consistent and satisfies the stated critical requirements. This paper concentrates on intralevel proofs.>

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.>

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.

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.

A technique and an environment-supporting specialization of generalized software components are described. The technique is based on symbolic execution. It allows one to transform a generalized software component into a more specific and more efficient component. Specialization is proposed as a technique that improves software reuse. The idea is that a library of generalized components exists and the environment supports a designer in customizing a generalized component when the need arises for reusing it under more restricted conditions. It is also justified as a reengineering technique that helps optimize a program during maintenance. Specialization is supported by an interactive environment that provides several transformation tools: a symbolic executor/simplifier, an optimizer, and a loop refolder. The conceptual basis for these transformation techniques is described, examples of their application are given, and how they cooperate in a prototype environment for the Ada programming language is outlined.>

The authors introduce a high-level Petri net formalism-environment/relationship (ER) nets-which can be used to specify control, function, and timing issues. In particular, they discuss how time can be modeled via ER nets by providing a suitable axiomatization. They use ER nets to define a time notation that is shown to generalize most time Petri-net-based formalisms which appeared in the literature. They discuss how ER nets can be used in a specification support environment for a time-critical system and, in particular, the kind of analysis supported.>

Some basic semantic issues of a language for a reliable and provably correct real-time programs are discussed. The language is based on E.W. Dijkstra's guarded commands and on a proposal by V.H. Haase (1981). Haase's proposal is assessed, its semantic consistencies are shown, and corrections are proposed that give a sound basis for a real-time language based on guarded commands.>

Chains (or cascade composition) of push-down transducers are introduced as a model of multi-pass compilers. We focus on deterministic chains, since nondeterministic transducer chains of length two define the recursively enumerable sets. Deterministic chains recognize in linear time a superset of context-free deterministic languages. This family is $\mathcal{CH}$ closed under Boolean operations, disjoint shuffle,and reverse deterministic pushdown translation, but not under homomorphism. Equivalent definitions of the family in terms of composition of syntax-directed translation schemes and control languages are considered. The family is a strict hierarchy ordered by the length of the chain. The complexity of $\mathcal{CH}$ is obviously linear, but not all linear-time parsable languages are in $\mathcal{CH}$. On the other hand it strictly includes the Boolean closure of deterministic languages. Finally $\mathcal{CH}$ is not comparable with another classical Boolean algebra of formal languages, namely real-time languages.

The notion of noncounting language, initially introduced for regular languages recognized by counter-free finite machines, and recently extended to parenthesized context-free languages, is here further studied for general (i.e., nonparenthesized) context-free languages. While weakly equivalent context-free grammars do not, in general, fall in the same class with respect to the noncounting property, it is shown by a complex proof that weakly equivalent operator precedence grammars are all counting or all noncounting (a property which distinguishes the operator precedence languages from classical deterministically parsable families).

The concept of incremental parsing is briefly introduced and motivated.A general shift-reduce incremental parser is presented and compared with the corresponding conventional parser in terms of speed of analysis and storage requirements.It is then shown that additional speed-up can be obtained in the particular case of LR parsing.It is suggested that the approach can be applied to other parsing algorithms and generalized to the whole compiling or interpreting process.

Separate compilation is a useful tool in the development, debugging, testing, and integration of modular systems.

An incremental parser is a device which is able to perform syntax analysis in an incremental way, avoiding complete reparsing of a program after each modification. The incremental parser presented extends the conventional LR parsing algorithm and its performance is compared with that of a conventional parser. Suggestions for an implementation and possible extensions to other parsing methods are also discussed.

The class of noncountlng (aperiodic) context-free parenthesis languages is introduced here and is found to extend the classical theory of noncountmg regular languages It Is proved that it is possible to decide whether or not a context-free parenthesis grammar Is noncountmg The class of k-distract-homogeneous grammars (previously introduced in connection with studies on grammatical mference or language acqmsitmn) is rigorously defined and proved to be noncountlng It as argued that the noncountmg model fits the syntactic aspects of natural or araficial languages more closely than the context-free model