Hybrid systems are interacting networks of digital and continuous systems. - brid systems arise throughout business and industry in areas such as interactive distributed simulation, trac control, plant process control, military command and control, aircraft and robot design, and path planning. Three of the fun- mental problems that hybrid systems theory should address are: How to model physical and information systems as hybrid systems; how to verify that their - havior satis es program or performance specic ations; and how to extract from performancespeci cationsforanetworkofphysicalsystemsandtheirsimulation models digital control programs which will force the network to obey its perf- mance speci cation. This rapidly developing area is at the interface of control, engineeringandcomputer science. Methods under developmentareextensionsof thosefromdiverseareassuchasprogramveri cation, concurrentanddistributed processes, logic programming, logics of programs, discrete event simulation, c- culus of variations, optimization, di erential geometry, Lie algebras, automata theory, dynamical systems, etc. When the rst LNCS volume Hybrid Systems was published in 1993, the e ect was to focus the attention of researchers worldwide on developing theory andengineeringtoolsapplicabletohybridsystemsinwhichcontinuousprocesses interact with digital programs in real time. At the time of publication of this fth volume, there is general agreement that this is an important area in which mathematics, control engineering, and computer science can be fruitfully c- bined. There are now hybrid system sections in many engineering and computer scienceinternationalmeetings, hybridsystems researchgroupsin manyuniver- ties and industrial laboratories, and also other excellent series of hybrid systems conferenc

Each year the Safety-critical Systems Symposium brings together practitioners and researchers in a quest to inculcate a higher degree of safety engineering into the development and operation of critical software-based systems. On this, the Symposium's seventh occasion, it explores recent work and experience which lead us further 'towards system safety'. This book of the Proceedings covers the entire event. The first paper is the course text of a tutorial run on the first day of the Symposium, included here to provide readers with a coverage of the entire event. The next fourteen papers were presented, on the second and third days, in six sessions: Safety Cases, Systems Engineering, Safety Analysis and Safety Integrity, Tools for Software Safety, Solving Safety Problems, and Qllestions and Competences. Eight of the fourteen papers were authored in industry, four in universities, and two in other research establishments. Four of them report on work outside the UK: in France, Germany, Norway and Brazil. There are three papers on safety cases, each taking a different perspective. Skogstad from Norway and Boyce and Hamilton of GEC-Marconi both report on experience in the field, the former in attempting to apply European norms to project documentation and the latter in attempting to build up a retrospective safety case. The third paper, by Goodman, takes a more philosophical stance, examining the lack of useful measurement in safety assurance.

This book constitutes the refereed proceedings of the 4th International Conference on Typed Lambda Calculi and Applications, TLCA'99, held in L'Aquila, Italy in April 1999. The 25 revised full papers presented were carefully reviewed and selected from a total of 50 submissions. Also included are two invited demonstrations. The volume reports research results on various aspects of typed lambda calculi. Among the topics addressed are noncommutative logics, type theory, algebraic data types, logical calculi, abstract data types, and subtyping.

ETAPS'99 is the second instance of the European Joint Conferences on Theory and Practice of Software. ETAPS is an annual federated conference that was established in 1998 by combining a number of existing and new conferences. This year it comprises ve conferences (FOSSACS, FASE, ESOP, CC, TACAS), four satellite workshops (CMCS, AS, WAGA, CoFI), seven invited lectures, two invited tutorials, and six contributed tutorials. The events that comprise ETAPS address various aspects of the system - velopment process, including speci cation, design, implementation, analysis and improvement. The languages, methodologies and tools which support these - tivities are all well within its scope. Dieren t blends of theory and practice are represented, with an inclination towards theory with a practical motivation on one hand and soundly-based practice on the other. Many of the issues involved in software design apply to systems in general, including hardware systems, and the emphasis on software is not intended to be exclusive.

State-transition systems model machines, programs, and speci?cations [20, 23,284,329],butalsothegrowthanddeclineofantpopulations,?nancial markets, diseases and crystals [22, 35, 178, 209, 279]. In the last decade, thegrowinguseofdigitalcontrollersinvariousenvironmentshasentailed theconvergenceofcontroltheoryandreal-timesystemstowardhybrids- tems [16] by combining both discrete-event facets of reality with Nature's continuous-time aspects. The computing scientist and the mathematician have re-discovered each other. Indeed, in the late sixties, the programming language Simula, "father" of modern object-oriented languages, had already been speci?cally designed to model dynamical systems [76]. Today,theimportanceofcomputer-basedsystemsinbanks,telecom- nication systems, TVs, planes and cars results in larger and increasingly complex models. Two techniques had to be developed and are now fruitfully used to keep analytic and synthetic processes feasible: composition and - straction.Acompositionalapproachbuildssystemsbycomposingsubsystems that are smaller and more easily understood or built. Abstraction simpli?es unimportantmattersandputstheemphasisoncrucialparametersofsystems. Inordertodealwiththecomplexityofsomestate-transitionsystemsand tobetterunderstandcomplexorchaoticphenomenaemergingoutofthe behaviorofsomedynamicalsystems,theaimofthismonographistopresent ?rststepstowardtheintegratedstudyofcompositionandabstractionin dynamical systems de?ned by iterated relations. Themaininsightsandresultsofthisworkconcernastructuralorm f of complexityobtainedbycompositionofsimpleinteractingsystemspresenting opposedattractingbehaviors.Thiscomplexityexpressesitselfintheevo- tionofcomposedsystems,i.e.,theirdynamics,andintherelationsbetween their initial and ?nal states, i.e., the computations they realize. The theor- ical results presented in the monograph are then validated by the analysis ofdynamicalandcomputationalpropertiesoflow-dimensionalprototypesof chaotic systems (e.g. Smale horseshoe map, Cantor relation, logistic map), high-dimensional spatiotemporally complex systems (e.g. cellular automata), and formal systems (e.g. paperfoldings, Turing machines). Acknowledgements. ThismonographisarevisionofmyPhDthesiswhichwas completed at the Universit' e catholique de Louvain (Belgium) in March 96. VIII Preface The results presented here have been in?uenced by many people and I would like to take this opportunity to thank them all.

Middleware is everywhere. Ever since the advent of sockets and other virtu- circuit abstractions, researchers have been looking for ways to incorporate high- value concepts into distributed systems platforms. Most distributed applications, especially Internet applications, are now programmed using such middleware platforms. Prior to 1998, there were several major conferences and workshops at which research into middleware was reported, including ICODP (International C- ference on Open Distributed Processing), ICDP (International Conference on Distributed Platforms) and SDNE (Services in Distributed and Networked - vironments). Middleware'98was a synthesis of these three conferences. Middleware 2000 continued the excellent tradition of Middleware'98. It p- vided a single venue for reporting state-of-the-art results in the provision of distributed systems platforms. The focus of Middleware 2000 was the design, implementation, deployment, and evaluation of distributed systems platforms and architectures for future networked environments. Among the 70 initial submissions to Middleware 2000, 21 papers were - lected for inclusion in the technical program of the conference. Every paper was reviewed by four members of the program committee. The papers were judged - cording to their originality, presentation quality, and relevance to the conference topics. The accepted papers cover various subjects such as caching, re?ection, quality of service, and transactions.

Preface VI I X Table of Contents B. Moeller and J.V. Tucker (Eds.): Prospects for Hardware Foundations, LNCS 1546, pp. 1-26, 1998. Springer-Verlag Berlin Heidelberg 1998 2 The NADA Group Introduction: NADA and NIL 3 4 The NADA Group Introduction: NADA and NIL 5 6 The NADA Group Introduction: NADA and NIL 7 8 The NADA Group Introduction: NADA and NIL 9 10 The NADA Group Introduction: NADA and NIL 11 12 The NADA Group Introduction: NADA and NIL 13 14 The NADA Group Introduction: NADA and NIL 15 16 The NADA Group Introduction: NADA and NIL 17 18 The NADA Group Introduction: NADA and NIL 19 20 The NADA Group Introduction: NADA and NIL 21 22 The NADA Group Introduction: NADA and NIL 23 24 The NADA Group Introduction: NADA and NIL 25 26 The NADA Group Streams, Stream Transformers and Domain Representations B. Moeller and J.V. Tucker (Eds.): Prospects for Hardware Foundations, LNCS 1546, pp. 27-68, 1998. Springer-Verlag Berlin Heidelberg 1998 28 J. Blanck, V. Stoltenberg-Hansen, and J.V. Tucker Streams, Stream Transformers and Domain Representations 29 30 J. Blanck, V. Stoltenberg-Hansen, and J.V. Tucker Streams, Stream Transformers and Domain Representations 31 32 J. Blanck, V. Stoltenberg-Hansen, and J.V. Tucker Streams, Stream Transformers and Domain Representations 33 34 J. Blanck, V. Stoltenberg-Hansen, and J.V. Tucker Streams, Stream Transformers and Domain Representations 35 36 J. Blanck, V. Stoltenberg-Hansen, and J.V. Tucker Streams, Stream Transformers and Domain Representations 37

but when we state that A 'equals' B , as well having to know what we mean by A and B we also have know what we mean by 'equals'. This section explores the role of observers; how different types of observ er see different things as being equal, and how we can produce algo rithms to decide on such equalities. It also explores how we go about writing specifications to which we may compare our SCCS designs. * The final section is the one which the students like best. Once enough of SCCS is grasped to decide upon the component parts of a design, the 'turning the handle' steps of composition and check ing that the design meets its specification are both error-prone and tedious. This section introduces the concurrency work bench, which shoulders most of the burden. How you use the book is up to you; I'm not even going to suggest path ways. Individual readers know what knowledge they seek, and course leaders know which concepts they are trying to impart and in what order.

Human Error and System Design and Management contains a collection of contributions presented at an international workshop with the same name held from March 24-26, 1999 at the Technical University of Clausthal, Germany. The purpose of this workshop was to discuss the results of a research project investigating the "Influences of Human-Machine-Interfaces on the Error-proneness of Operator Interaction with Technical Systems" in a broad context. Therefore experts from academia and industry were invited to participate so that practical as well as theoretical aspects of the subject matter were covered. Topics included recent considerations concerning multimedia and ecological interfaces as well as situation awareness.
This book contains the current thinking on this discussion and can be regarded as a supplement to engineers and researchers who are active in the area of human machine interfaces.

There is hardly a science that is without the notion of "system." We have systems in mathematics, formal systems in logic, systems in physics, electrical and mechanical engineering, architectural-, operating-, infonnation-, programming systems in computer science, management-and PJoduction systems in industrial applications, economical-, ecological-, biological systems, and many more. In many of these disciplines formal tools for system specification, construction, verification, have been developed as well as mathematical concepts for system modeling and system simulation. Thus it is quite natural to expect that systems theory as an interdisciplinary and well established science offering general concepts and methods for a wide variety of applications is a subject in its own right in academic education. However, as can be seen from the literature and from the curricula of university studies -at least in Central Europe-, it is subordinated and either seen as part of mathematics with the risk that mathematicians, who may not be familiar with applications, define it in their own way, or it is treated separately within each application field focusing on only those aspects which are thought to be needed in the particular application. This often results in uneconomical re-inventing and re-naming of concepts and methods within one field, while the same concepts and methods are already well introduced and practiced in other fields. The fundamentals on general systems theory were developed several decades ago. We note the pioneering work of M. A. Arbib, R. E. Kalman, G. 1. Klir, M. D.

Formal methods are coming of age. Mathematical techniques and tools are now regarded as an important part of the development process in a wide range of industrial and governmental organisations. A transfer of technology into the mainstream of systems development is slowly, but surely, taking place. FM'99, the First World Congress on Formal Methods in the Development of Computing Systems, is a result, and a measure, of this new-found maturity. It brings an impressive array of industrial and applications-oriented papers that show how formal methods have been used to tackle real problems. These proceedings are a record of the technical symposium ofFM'99: alo- side the papers describingapplicationsofformalmethods, youwill ndtechnical reports, papers, andabstracts detailing new advances in formaltechniques, from mathematical foundations to practical tools. The World Congress is the successor to the four Formal Methods Europe Symposia, which in turn succeeded the four VDM Europe Symposia. This s- cession re?ects an increasing openness within the international community of researchers and practitioners: papers were submitted covering a wide variety of formal methods and application areas. The programmecommittee re?ects the Congress's international nature, with a membership of 84 leading researchersfrom 38 di erent countries.The comm- tee was divided into 19 tracks, each with its own chair to oversee the reviewing process. Our collective task was a di cult one: there were 259 high-quality s- missions from 35 di erent countries.

The monograph is concerned with computational methods for controller design that allow several typical performance specifications to be directly imposed on a system. The general approach proposed, is applicable to a large class of problems; it is based on posing multi-objective control problems as convex infinite dimensional optimization problems. Particularly interesting and useful are the following methodological as pects of the approach proposed in the monograph. These are: A unified way to pose the problems as generalized linear programs. Duality theory results that characterize the duality relationship for the generalized linear programs arising from multi-objective control problems. A set of tools to analyse the convergence properties of the computational method based on the duality relationship. The complete analysis and extension of methods developed for the L1 problem, for several important multi-objective problems. This book is primarily concerned with multi-objective control problems as convex optimizations on the space of the closed loop maps. However, the issue of deriving exact or approximate solutions is similar when the problems are posed as dynamic games in s tate space. Therefore the problem of finding the state feedback controller that minimizes the worst-case peak-to-peak amplification of the closed loop system, is considered in the last chapter. The objective of this work is to propose generic computation methods that can be used to solve a wide range of multi-objective control problems. Infinite dimensional convex optimization problems are considered, giving the book a broader focus than other competitive titles in this field. This non-exclusive approach will have a wide appeal for scientists and graduate students. They will be able to determine and analyse readily implementable computational methods to derive exact or approximate solutions. Key words for the catalogue index: Controller design, multi objective control, computational methods, linear programming, robust control.USPs: Generic computational methods are proposed - these can be used to solve a wide range of multi-objective control p roblems.A new computational method for the L1 problem is suggested, which is superior to existing approaches and is based on the solution of a mixed objective problem.The reader will greatly benefit from the comprehensive treatment of this topic

This book constitutes the refereed proceedings of the 10th International Conference on Advanced Information Systems Engineering, CAiSE'98, held in Pisa, Italy, in June 1998.
The book presents 21 revised full papers together with one invited survey; the papers were selected from a total of 102 submissions. The book is divided into sections on information systems design, data warehouses and extensible database management systems, workflow management and groupware, reuse, application design and WWW, and industrial experiences.

Formal methods are coming of age. Mathematical techniques and tools are now regarded as an important part of the development process in a wide range of industrial and governmental organisations. A transfer of technology into the mainstream of systems development is slowly, but surely, taking place. FM'99, the First World Congress on Formal Methods in the Development of Computing Systems, is a result, and a measure, of this new-found maturity. It brings an impressive array of industrial and applications-oriented papers that show how formal methods have been used to tackle real problems. These proceedings are a record of the technical symposium ofFM'99: alo- side the papers describingapplicationsofformalmethods, youwill ndtechnical reports, papers, andabstracts detailing new advances in formaltechniques, from mathematical foundations to practical tools. The World Congress is the successor to the four Formal Methods Europe Symposia, which in turn succeeded the four VDM Europe Symposia. This s- cession re?ects an increasing openness within the international community of researchers and practitioners: papers were submitted covering a wide variety of formal methods and application areas. The programmecommittee re?ects the Congress's international nature, with a membership of 84 leading researchersfrom 38 di erent countries.The comm- tee was divided into 19 tracks, each with its own chair to oversee the reviewing process. Our collective task was a di cult one: there were 259 high-quality s- missions from 35 di erent countries.

This book consitutes the refereed proceedings of the 4th International Conference on Mathematics of Program Construction, MPC'98, held in Marstrand, near Goteborg, Sweden, in June 1998. The 17 revised full papers presented were selected from 57 submissions; also included are three invited contributions. The volume is devoted to the use of crisp, clear mathematics in the discovery and design of algorithms and in the development of corresponding software and hardware; varoius approaches to formal methods for systems design and analysis are covered.

This book constitutes the refereed proceedings of the First International Workshop on Hybrid Systems: Computation and Control, held in Berkeley, California, USA, in April 1998.
The volume presents 27 revised full papers selected from a total of 55 submissions. The papers focus on mathematical methods for the rigorous and systematic design and analysis of hybrid systems. Hybrid systems consist of digital devices that interact with analog environments; they are particularly important in context with safety-critical systems and dependable computing. The present volume extends the line of hybrid systems research documented in volumes 736, 999, 1066, 1201, and 1273 of the LNCS series.

This book constitutes the refereed proceedings of the 4th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS'98, held in conjunction with ETAPS in Lisbon, Portugal, in March/April 1998. The 28 revised full papers presented together with an invited talk were selected from a total of 78 submissions. The volume is devoted to conceptual foundations, development, and applications of tools and algorithms for the specification, verification, analysis, and construction of software and hardware systems. The papers are organized in sections on model checking, design and architecture, various applications, fielded applications, verification of real-time systems, mixed analysis techniques, and case studies and experience.

Written by psychologists, this book focuses on the design of computer systems from the perspective of the user. The authors place human beings firmly at the centre of system design and so assess their cognitive and physical attributes as well as their social needs. The model used specifically takes into consideration the way in which computer technology needs to be designed in order to take account of all these human factors.
The text comprises a careful mix of theory and applications and is spiced throughout with practical examples of do's and don'ts in designing systems.

This book constitutes the refereed proceedings of the 11th International Conference on Computer Aided Verification, CAV'99, held in Trento, Italy in July 1999 as part of FLoC'99.
The 34 revised full papers presented were carefully reviewed and selected from a total of 107 submissions. Also included are six invited contributions and five tool presentations. The book is organized in topical sections on processor verification, protocol verification and testing, infinite state spaces, theory of verification, linear temporal logic, modeling of systems, symbolic model checking, theorem proving, automata-theoretic methods, and abstraction.

The fields of control and robotics are now at an advanced level of maturity both in theory and practice. Numerous systems are used effectively in industrial production and other sectors of modern life. This volume contains a well-balanced collection of over fifty papers focusing on analysis and design problems. The current trends and advances in the fields are reflected. Topics covered include: system analysis, identification and stability optimal, adaptive, robust and QFT controller design design and application of driving simulators industrial robots and telemanipulators mobile, service, and legged robots virtual reality in robotics The book brings together important original results derived from a variety of academic and engineering environments. Also, it serves as a timely reference volume for the researcher and practitioner.

This volume originates from the School on Embedded Systems held in Veldhoven, The Netherlands, in November 1996 as the first event organized by the European Educational Forum. Besides thoroughly reviewed and revised chapters based on lectures given during the school, additional papers have been solicited for inclusion in the present book in order to complete coverage of the relevant topics.
The authors adress professionals involved in the design and management of embedded systems in industry as well as researchers and students interested in a competent survey. The book will convince the reader that many architectural and algorithmic problems in the area of embedded systems have well documented optimal or correct solutions, notably in the fields of real-time computing, distributed computing, and fault-tolerant computing.

This book constitutes the refereed proceedings of the 5th International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems, FTRTFT'98, held in Lyngby, Denmark, in September 1998.
The 22 revised full papers presented were carefully selected and reviewed for inclusion in the book. Also included are four invited contributions and five tool demonstrations. The papers address the current aspects of the hot topic of embedded systems, in particular temporal logic, requirements engineering, analysis techniques, verification, model checking, and applications.

An increasing recognition of the role of the human-system interface is leading to new extensions and styles of specification. Techniques are being developed that facilitate the expression of user-oriented requirements and the refinement and checking of specifications of interactive systems. This book reflects the state of the art in this important area and also contains a summary of working group discussions about how the various techniques represented might be applied to a common case study.

The Sorbonne University is very proud to host this year the oms Conference on Object Oriented Information Systems. There is a growing awareness of the importance of object oriented techniques, methods and tools to support information systems engineering. The term information systems implies that the computer based systems are designed to provide adequate and timely information to human users in organizations. The term engineering implies the application of a rigorous set of problem solving approaches analogous to those found in traditional engineering disciplines. The intent of this conference is to present a selected number of those approaches which favor an object oriented view of systems engineering. oms '98 is the fifth edition of a series of conferences. Starting in 1994 in London, this series evolved from a British audience to a truly European one. The goal is to build a world wide acknowledged forum dedicated to object oriented information systems engineering. This conference is organized with the aim to bring together researchers and practitioners in Information Systems, Databases and Software Engineering who have interests in object oriented information systems. The objective is to advance understanding about how the object technology can empower information systems in organizations, on techniques for designing effective and efficient information systems and methods and development tools for information systems engineering. The conference aims also at discussing the lessons learned from large scale projects using objects. The call for oms was given international audience.

Correct Systems looks at the whole process of building a business process model, capturing that in a formal requirements statement and developing a precise specification. The issue of testing is considered throughout the process and design for test issues are fundamental to the approach. A model (language) and a methodology are presented that is very powerful, very easy to use and applicable for the "new world" of component based systems and the integration of systems from dependable components. This book discusses a new area which will be of interest to both software and hardware designers. It presents specification, design, implementation and testing in a user-oriented fashion using simple formal and diagramming techniques with a high level of user-friendliness. The first part provides a simple introduction to the method together with a complete, real case study. The second part describes, in detail, the mathematical theory behind the methods and the claims made.