Egon Börger

Quelli che s'innamoran di pratica senza scienzia sono come 'l nocchieri ch'entra in navilio sanza timone o bussola, 1 che mai ha certezza dove si vada. - Leonardo da Vinci Ich habe oft bemerkt, dass wir uns durch allzuvieles Symbolisieren 2 die Sprache fu ..r die Wirklichkeit untu ..chtig machen. - Christian Morgenstern This is the place to express our thanks. First of all we thank all those who over the years have actively contributed to shaping the novel software design and analysis method explained in this book. They are too numerous to be mentioned here. They all appear in some way or the other on the following pages, in particular in the bibliographical and historical Chap. 9 which can be read independently of the book. We then thank those who have helped with detailed critical comments on the draft chapters to shape the way our arguments are presented in this book: M. B.. orger (Diron Mu ..nster), I. Craggs (IBMHursley),G. DelCastillo(SiemensMunc .. hen),U. Gl. asser(SimonFraser University, Vancouver,Canada),J. Huggins(Kettering University,Michigan, USA), B. Koblinger (IBM Heidelberg), P. Pa ..ppinghaus (Siemens Munc .. hen), A. Preller (Universit' e de Montpellier, France), M. -L. Potet (INP de Gre- ble, France),W. Reisig (Humboldt-Universit. at zu Berlin, Germany),H. Rust (Universit. at Cottbus, Germany), G. Schellhorn (Universit. at Augsburg, G- many), B. Thalheim (Universit. at Cottbus, Germany) and a dozen student generationsat Universita 'di Pisa. We thankM. Barmet(ETH Zur .. ich)for her solutions of the exercises in Chap. 8. We also thank L.

Structures of Computing explains the behavioral meaning of fundamental concepts of computing from a practical viewpoint and in generic terms, unrestricted by specific computing devices or programming languages. To compute is understood as processing structures by a set of cooperating agents each of which executes an algorithm assigned to it and interacts with the other agents. Part I of the book defines the conceptual constituents of interactive processes: (i) data, i.e. structured objects with associated properties, relations and functions the algorithmic processes operate upon, (ii) basic operations that affect the data in single execution steps, and (iii) control mechanisms that determine the combination of single steps in multi-agent computations where the interaction happens via communication or other forms of data sharing. Part II analyses these constituents concerning (i) methods to achieve process correctness (inspection, experimental validation, reasoning), (ii) principal computational paradigms (architectures, programming styles, communication structures, control patterns from sequential and reflective to concurrent, mixed synchronous/asynchronous and data flow control), and (iii) complexity (power and limits of computing structures). The book is mainly addressed to students and professionals who want to understand the conceptual foundation of computing. It does not assume any specific programming experience but only a basic understanding of what are mechanically executable processes and their descriptions. Any unnecessary formalism is thus avoided, and definitions are formulated as much as possible in natural language, using common mathematical notation only where needed to prevent ambiguities. Numerous examples and exercises serve as comprehension checkpoints.

This book uses a variety of applications to illustrate a modeling method that helps practitioners to manage complex software-intensive systems. The proposed method relies on the combination of its abstraction concept and its operational character, with behavioral models in the precise and simple form of Abstract State Machines (ASMs).The book introduces both the modeling method (Part I) and the available tool support (Part II): In Part I the authors detail (using numerous examples) how to construct, explain, debug, explore, extend and reuse accurate system design models, starting from scratch. Only an elementary knowledge of common mathematical (including set-theoretic) notation and some basic experience with computational processes (systems, programs, algorithms) is assumed. Part II then shows how the modeling method can be supported by implementing tools that make design models executable and debuggable.To illustrate how to build, debug and maintain systems and to explain their construction in a checkable manner, a general, problem-oriented refinement method is adopted to construct system models from components. The method starts with abstract models and refines them step by step, incrementally adding further details that eventually lead to code.Intended for practitioners who build software intensive systems, and students specializing in software engineering, it can be used both for self-study and for teaching, and it can serve as a reference book. Exercises are included to help readers check their understanding of the explained concepts. For many models defined in the book, refinements to executable versions can be downloaded for experimental validation from the book’s website at http://modelingbook.informatik.uni-ulm.de

Activities performed in organizations are coordinated via communication between the people involved. The sentences used to communicate are naturally structured by subject, verb, and object. The subject describes the actor, the verb the action and the object what is affected by the action. Subject-oriented Business Process Management (S-BPM) as presented in this book is based on this simple structure which enables process-oriented thinking and process modeling. S-BPM puts the subject of a process at the center of attention and thus deals with business processes and their organizational environment from a new perspective, meeting organizational requirements in a much better way than traditional approaches. Subjects represent agents of an action in a process, which can be either technical or human (e.g. a thread in an IT system or a clerk). A process structures the actions of each subject and coordinates the required communication among the subjects. S-BPM provides a coherent procedural framework to model and analyze business processes: its focus is the cooperation of all stakeholders involved in the strategic, tactical, and operational issues, sharing their knowledge in a networked structure. The authors illustrate how each modeling activity through the whole development lifecycle can be supported through the use of appropriate software tools. The presentation style focuses on professionals in industry, and on students specializing in process management or organizational modeling. Each chapter begins with a summary of key findings and is full of examples, hints, and possible pitfalls. An interpreter model, a toolbox, and a glossary summarizing the main terms complete the book. The web site www.i2pm.net provides additional software tools and further material.

The origin of this book goes back to the Dagstuhl seminar on Logic for System Engineering, organized during the first week of March 1997 by S. Jiihnichen, J. Loeckx, and M. Wirsing. During that seminar, after Egon Borger's talk on How to Use Abstract State Machines in Software Engineering, Wolfram Schulte, at the time a research assistant at the University of Ulm, Germany, questioned whether ASMs provide anything special as a scientifically well­ founded and rigorous yet simple and industrially viable framework for high­ level design and analysis of complex systems, and for natural refinements of models to executable code. Wolfram Schulte argued, referring to his work with K. Achatz on A Formal Object-Oriented Method Inspired by Fusion and Object-Z [1], that with current techniques of functional programming and of axiomatic specification, one can achieve the same result. An intensive and long debate arose from this discussion. At the end of the week, it led Egon Borger to propose a collaboration on a real-life specification project of Wolfram Schulte's choice, as a comparative field test of purely functional­ declarative methods and of their enhancement within an integrated abstract state-based operational (ASM) approach. After some hesitation, in May 1997 Wolfram Schulte accepted the offer and chose as the theme a high-level specification of Java and of the Java Virtual Machine.

Quelli che s'innamoran di pratica senza scienzia sono come 'l nocchieri ch'entra in navilio sanza timone o bussola, 1 che mai ha certezza dove si vada. - Leonardo da Vinci Ich habe oft bemerkt, dass wir uns durch allzuvieles Symbolisieren 2 die Sprache fu ..r die Wirklichkeit untu ..chtig machen. - Christian Morgenstern This is the place to express our thanks. First of all we thank all those who over the years have actively contributed to shaping the novel software design and analysis method explained in this book. They are too numerous to be mentioned here. They all appear in some way or the other on the following pages, in particular in the bibliographical and historical Chap. 9 which can be read independently of the book. We then thank those who have helped with detailed critical comments on the draft chapters to shape the way our arguments are presented in this book: M. B.. orger (Diron Mu ..nster), I. Craggs (IBMHursley),G. DelCastillo(SiemensMunc .. hen),U. Gl. asser(SimonFraser University, Vancouver,Canada),J. Huggins(Kettering University,Michigan, USA), B. Koblinger (IBM Heidelberg), P. Pa ..ppinghaus (Siemens Munc .. hen), A. Preller (Universit' e de Montpellier, France), M. -L. Potet (INP de Gre- ble, France),W. Reisig (Humboldt-Universit. at zu Berlin, Germany),H. Rust (Universit. at Cottbus, Germany), G. Schellhorn (Universit. at Augsburg, G- many), B. Thalheim (Universit. at Cottbus, Germany) and a dozen student generationsat Universita 'di Pisa. We thankM. Barmet(ETH Zur .. ich)for her solutions of the exercises in Chap. 8. We also thank L.

Activities performed in organizations are coordinated via communication between the people involved. The sentences used to communicate are naturally structured by subject, verb, and object. The subject describes the actor, the verb the action and the object what is affected by the action. Subject-oriented Business Process Management (S-BPM) as presented in this book is based on this simple structure which enables process-oriented thinking and process modeling. S-BPM puts the subject of a process at the center of attention and thus deals with business processes and their organizational environment from a new perspective, meeting organizational requirements in a much better way than traditional approaches. Subjects represent agents of an action in a process, which can be either technical or human (e.g. a thread in an IT system or a clerk). A process structures the actions of each subject and coordinates the required communication among the subjects. S-BPM provides a coherent procedural framework to model and analyze business processes: its focus is the cooperation of all stakeholders involved in the strategic, tactical, and operational issues, sharing their knowledge in a networked structure. The authors illustrate how each modeling activity through the whole development lifecycle can be supported through the use of appropriate software tools. The presentation style focuses on professionals in industry, and on students specializing in process management or organizational modeling. Each chapter begins with a summary of key findings and is full of examples, hints, and possible pitfalls. An interpreter model, a toolbox, and a glossary summarizing the main terms complete the book. The web site www.i2pm.net provides additional software tools and further material.

This book is addressed to all those - logicians, computer scientists, mathe­ maticians, philosophers of science as well as the students in all these disci­ plines - who may be interested in the development and current status of one of the major themes of mathematical logic in the twentieth century, namely the classical decision problem known also as Hilbert's Entscheidungsproblem. The text provides a comprehensive modern treatment of the subject, includ­ ing complexity theoretic analysis. We have made an effort to combine the features of a research monograph and a textbook. Only the basic knowledge of the language of first-order logic is required for understanding of the main parts of the book, and we use standard terminology. The chapters are written in such a way that various combinations of them can be used for introductory or advanced courses on undecidability, decidability and complexity of logical decision problems. This explains a few intended redundancies and repetitions in some of the chapters. The annotated bibliography, the historical remarks at the end of the chap­ ters and the index allow the reader to use the text also for quick reference purposes.

The origin of this book goes back to the Dagstuhl seminar on Logic for System Engineering, organized during the first week of March 1997 by S. Jiihnichen, J. Loeckx, and M. Wirsing. During that seminar, after Egon Borger's talk on How to Use Abstract State Machines in Software Engineering, Wolfram Schulte, at the time a research assistant at the University of Ulm, Germany, questioned whether ASMs provide anything special as a scientifically well­ founded and rigorous yet simple and industrially viable framework for high­ level design and analysis of complex systems, and for natural refinements of models to executable code. Wolfram Schulte argued, referring to his work with K. Achatz on A Formal Object-Oriented Method Inspired by Fusion and Object-Z [1], that with current techniques of functional programming and of axiomatic specification, one can achieve the same result. An intensive and long debate arose from this discussion. At the end of the week, it led Egon Borger to propose a collaboration on a real-life specification project of Wolfram Schulte's choice, as a comparative field test of purely functional­ declarative methods and of their enhancement within an integrated abstract state-based operational (ASM) approach. After some hesitation, in May 1997 Wolfram Schulte accepted the offer and chose as the theme a high-level specification of Java and of the Java Virtual Machine.

Endlich liegt der ,,Klassiker" der Theoretischen Informatik, der Studenten und Forschern ein unentbehrliches Standardwerk ist, in neuer Auflage vor.

Thema dieses Buches sind zwei schon Voh Leibniz als zusammengehoerend erkannte Begriffe, deren mathematische Entwicklung von Frege bis Turing das theoretische Fundament der Computerwissenschaft gelegt hat: der Be- griff formaler Sprache als Trager prazisen Ausdrucks von Bedeutungen, Sach- verhalten, Problemen und der des Algorithmus oder Kalkuls, d. h. formal ope- rierender Verfahren zur Loesung prazis beschriebener Fragen und Probleme. Das Buch gibt eine einheitliche Einfuhrung in die moderne Theorie dieser Begriffe, wie sie sich zuerst in der mathematischen Logik und der Berechen- barkeitstheorie und weiter in der Automatentheorie, der Theorie formaler Sprachen und der Komplexitatstheorie entwickelt hat. Neben der Berucksich- tigung eines schon klassisch gewordenen Grundkanons dieser Gebiete ist die Stoffauswahl mit der Absicht getroffen worden, durchgangig Erneuerungen traditioneller Fragestellungen, Ergebnisse und Methoden den Vorrang zu ge- ben, die sich aus Bedurfnissen oder Erkenntnissen der Informatik und hier besonders der Komplexitatstheorie heraus entwickelt haben. Die Zielsetzung dieses Buches ist eine doppelte: Lehrbuch zu sein. fur Anfangervorlesungen zu den genannten Gebieten, wie sie in fast allen Curri- cula der Informatik, der Logik und der Mathematik heute auftreten, aber daruberhinaus auch Monographie, indem in systematischer Absicht in jedem der angesprochenen Gebiete weiterfuhrende Ergebnisse neuerer Forschungen (grossenteils erstmalig in lehrbuchartiger Form) vorgefuhrt werden und uber- all versucht wird, Analogien und Zusammenhange zwischen verschiedenen Be- griffen und Konstruktionen explizit herauszuarbeiten.