Semantics of Parallelism: Non-Interleaving Representation of Behaviour

ISBN-13: 9783540760597 / Angielski / Miękka / 1997 / 473 str.

M. W. Shields; Michael W. Shieds; Michael W. Shields

Opis

Semantics of Parallelism is the only book which provides a unified treatment of the non-interleaving approach to process semantics (as opposed to the interleaving approach of the process algebraists). Many results found in this book are collected for the first time outside conference and journal articles on the mathematics of non-interleaving semantics. It gives the reader a unified view of various attempts to model parallelism within one conceptual frame work. It is aimed at postgraduates in theoretical computer science and academics who are teaching and researching in the modelling of discrete, concurrent/distributed systems. Workers in the information technology industry who are interested in available theoretical studies on parallelism will also be interested in this book.

Spis treści

1. Whys and Wherefores.- 1.1. Why Models of Parallelism ?.- 1.2. Specification in a Variety of Styles.- 1.3. An Overview of the Basic Model.- 1.4. The Contents of the Book.- 2. Behavioural Presentations.- 2.1. Introduction.- 2.2. Examples.- 2.3 Basic Properties of Behavioural Presentations.- Notes.- 3. Discrete Behavioural Presentations.- 3.1. Introduction: Zeno’s Paradoxes.- 3.2. Discreteness.- 3.3. A Characterisation of Discrete Behavioural Presentations.- Notes.- 4. Order Theoretic Properties of Left-Closed Behavioural Presentations.- 4.1. Introduction.- 4.2. Consistent Completeness.- 4.3. Prime Algebraicity.- Notes:.- 5. Event Structures and Closures of Behavioural Presentations.- 5.1 Introduction.- 5.2. Event Structures and Behavioural Presentations.- 5.3. Closure of Behavioural Presentations.- Notes.- 6. Another Event Structure Model.- 6.1 Introduction.- 6.2. The Model.- 6.3. Behavioural Presentations Which Represent Event Structures.- Notes.- 7. Properties of Behavioural Presentations.- 7.1. Introduction.- 7.2. Asynchrony.- 7.3. Left-Closure and Discreteness.- 7.4. Determinacy.- 7.5. Concurrency.- 7.6. Closure.- 8. Karp and Miller Computation Graphs.- 8.1. Introduction.- 8.2. The Model and its Node-Set Sequence Semantics.- 8.3. Behavioural Presentation Semantics.- 8.4. Comparing the Semantics.- Notes.- 9. Trace and Vector Languages.- 9.1. Introduction.- 9.2. Basic Definitions and Properties.- 9.3. Equivalence of the Models.- Notes.- 10. Order Theoretic Properties of Vector Languages.- 10.1. Introduction.- 10.2. Consistent Completeness.- 10.3. Prime Algebraicity.- 10.4. Left-Closed Vector Languages.- 10.5. Parallel Composition.- Notes.- 11. Determinacy.- 11.1. Introduction.- 11.2. Strongly Forward Stable Vector Languages.- 11.3. Simple Vector Languages.- Notes.- 12. Linguistic Behavioural Presentations.- 12.1. Introduction.- 12.2. The Structure of BL,A.- 12.3. Strong Forward Stability Revisited.- Notes.- 13. Unambiguous Transition Systems.- 13.1. Introduction.- 13.2. Transition Systems.- 13.3. Properties of Unambiguous Transition Systems.- 13.4. Bisimulation.- 13.5. Computation Graphs Revisited.- Notes.- 14. General Transition Systems.- 14.1. Introduction.- 14.2. Behaviour of Transition Systems.- 14.3. Strong Equivalence.- 14.4. Strict Equivalence.- 15. Asynchronous Transition Systems.- 15.1. Introduction.- 15.2. The Automata.- 15.3. Equivalences. 187 Notes.- 16. Condition/Event Systems: Process and Occurrence Net Semantics.- 16.1. Introduction.- 16.2. Net Theory, C/E Systems and Process Semantics.- 16.3. Occurrence Net Semantics.- Notes.- 17. Condition/Event Systems: Asynchronous Transition System Semantics.- 17.1. Introduction.- 17.2. Asynchronous Transition System Semantics.- 17.3. Comparison of the Semantics: Preliminaries.- 17.4. From Behavioural Presentations to Processes….- 17.5…And Back Again.- 18. Loosely Coupled Systems.- 18.1. Introduction.- 18.2. Pure Loosely Coupled Systems.- 18.3. Loosely Coupled Systems with Transitions.- 19. Categorical Connections.- 19.1. Introduction.- 19.2. Asynchronous Transition Systems.- 19.3. Trace Languages.- 19.4. Discrete Behavioural Presentations.- 20. Categorical Applications.- 20.1. Introduction.- 20.2. Reduction Morphisms.- 20.3. Products.- 21. An Application: Realisation by Nets.- 21.1. Introduction.- 21.2. Conditions for Realisation.- 21.3. Representation of Loosely Coupled Systems.- Notes.- 22. Hybrid Transition Systems.- 22.1. Introduction.- 22.2. The Model.- 22.3. Classes of Hybrid Transition Systems.- Notes.- 23. The Keller Parallel Computation Model.- 23.1. Introduction.- 23.2. The Model and its Transition System Semantics.- 23.3. A Hybrid Transition System Semantics for General.- Nets.- 23.4. Hybrid Transition System Semantics for Parallel Programs.- 23.5. Comparison of the Semantics.- Notes.- 24. From Path Expressions to TCSP.- 24.1. Introduction.- 24.2. Syntax and Marked, Labelled Net Semantics.- 24.3. Hybrid Transition System Semantics.- 24.4. Comparison of the Semantics.- 24.5. Embedding COSY Into TCSP.- Notes.- 25. The Nivat/Arnold Process Model.- 25.1. Introduction.- 25.2. The Model and its Vector Semantics.- 25.3. Process Structure.- 25.4. Hybrid Transition System Semantics.- 25.5. Comparison with the Path/Process Notation.- 25.6. Process Structure and Occurrence Nets.- Notes.- 26. Constructions on Hybrid Transition Systems.- 26.1. Introduction.- 26.2. Recursion.- 26.3 Non-Recursive Constructions.- Notes.- 27. Process Calculus (CCS).- 27.1. Introduction.- 27.2. Syntax and Transition System Semantics.- 27.3. Hybrid Transition System Semantics.- 27.4. Properties of Expressions.- 27.5. Comparison of the Semantics.- Notes.- 28. Theoretical CSP.- 28.1. Introduction.- 28.2. TCSP and its Failure/Divergence Semantics.- 28.3. Hybrid Transition System Semantics.- 28.4. Comparison of the Semantics.- 28.5. Extending the Hybrid Transition System Semantics.- Notes.- 29. Conclusions: Theories of Parallelism.- Appendix. Review of Mathematical Prerequisites.- References.