Chris Tofts
Abstract
Abstract
A probabilistic calculus, derived from Milner's SCCS, WSCCS is presented. We define a notion of bisimulation for probabilistic processes and show that it is a congruence. A simple equational characterisation is shown to be both sound and complete for finite processes. We present many examples including some extended ones. The larger examples show both the expressive power of WSCCS and the availability of simple proof methods for some complex systems.
- [BBK86] Syntax and defining equations for an interrupt mechanism in process algebraFundamenta Informatica1986IX127168Google Scholar
- [CAM90] Chen, L., Anderson S. and Moller F.: A Timed Calculus of Communicating Systems, Research Report, Dept. Of Computer Science, Edinburgh University, LFCS-127, 1990Google Scholar
- [Cam89] Cammilleri. J.: Introducing a Priority Operator to CCS, Computer Laboratory Technical Report, Cambridge University, 1989.Google Scholar
- [Chr90] Christoff, I.: Testing Equivalences and Fully Abstract Models for Probabilistic Processes,in Proceedings Concur '90, LNCS 458, 1990.Google Scholar
- [GrS82] Grimmet, G.R. and Stirzaker D.R.,Probability and Random Processes, Oxford Science Publications, 1982.Google Scholar
- [GSS90] van Glabbek, R., Smolka S. A., Steffen B. and Tofts C.: Reactive, Generative and Stratified Models of Probabilistic Processes,in proceedings LICS 1990, 1990.Google Scholar
- [Hoa85] Hoare C. A. R.,Communicating Sequential Processes, Prentice-Hall 1985.Google Scholar
- [HeR90] Hennessey M. and Regan T.: A Temporal Process Algebra, Technical Report, Department of Cognitive Science, Sussex University, 1990.Google Scholar
- [HTF91] Hatcher, M., Tofts C. and Franks N.: Mutual Exclusion as a Mechanism for Information Exchange in Ant Nests,in Proceedings of the First European Conference on Social Insects, 1991.Google Scholar
- [Jon90] Jones, C.C.M.:Probabilistic Non-determinism, PhD Thesis University of Edinburgh, 1990.Google Scholar
- [Kei] Keilson, J.:Markov Chain Models — Rarity and exponentiality, Applied Mathematical Sciences 28, Springer Verlag.Google Scholar
- [JoS90] Jou, C. and Smolka S.: Equivalences, Congruences and Complete Axiomatizations for Probabilistic Processes,in Proceedings Concur '90, LNCS 458, 1990.Google Scholar
- [LaS89] Larsen, K.G. and Skou A.: Bisimulation through probabilistic testing,in proceedings POPL 1989, 1989.Google Scholar
- [Mil83] Calculi for Synchrony and AsynchronyTheoretical Computer Science1983253267310Google ScholarCross Ref
- [Mil90] Milner, R.:Communication and Concurrency, Prentice Hall, 1990.Google Scholar
- [MoT90] Moller, F., and Tofts C.: A Temporal Calculus of Communicating Systems,in proceedings Concur '90, LNCS 458, 1990.Google Scholar
- [Plo81] Plotkin, G.D.: A structured approach to operational semantics. Technical report Daimi Fn-19, Computer Science Department, Aarhus University. 1981.Google Scholar
- [ReR86] Reed, G., and Roscoe W.: A Timed Model for CSP,inProceedings ICALP '86, LNCS 226, 1986.Google Scholar
- [SmS90] Smolka, S., and Steffen B.: Priority as Extremal Probability,in proceedings Concur '90, LNCS 458, 1990.Google Scholar
- [SST89] Smolka, S., Steffen B. and Tofts C.: unpublished notes. Working title, Probability + Restriction ⇒ priority.Google Scholar
- [THF92] Tofts,C., Hatcher M.J., Franks N.: Autosynchronisation in Leptothorax Acervorum; Theory, Testability and Experiment,Journal of Theoretical Biology 157: 71–82.Google Scholar
- [ToF92] Tofts, C., and Franks N.: Doing the Right Thing: Ants, Bees and Naked Mole Rats,Trends in Evolution and Ecology 7: 346–349.Google Scholar
- [Tof89] Tofts, C.: Timing Concurrent Processes, LFCS-report. number 103, 1989.Google Scholar
- [Tof90a] Tofts, C.: A Synchronous Calculus of Relative Frequency,in proceedings CONCUR '90, Springer Verlag, LNCS 458, 1990Google Scholar
- [Tof90b] Tofts, C.: The Autosynchronisation ofLeptothorax Acervorum (Fabricius) Described in WSCCS, LFCS-Report Number 128.Google Scholar
- [Tof91] Tofts, C.: Task Allocation in Monomorphic Ant Species, LFCS-Report Number 128.Google Scholar
- [Tof93] Tofts, C.: Using Process Algebra to Descirbe Social Insect Behaviour,Transactions of the Society for Computer Simulation, 1993.Google Scholar
- [Yiw90] Real-Time Behaviour of Asynchronous Agentsin proceedings Concur '90, LNCS1990458502520Google Scholar
Index Terms
- Processes with probabilities, priority and time
Recommendations
Priority and abstraction in process algebra
More than 15 years ago, Cleaveland and Hennessy proposed an extension of the process algebra CCS in which some actions may take priority over others. The theory was equipped with a behavioral congruence based on strong bisimulation. This article gives a ...
Priority as extremal probability
AbstractWe extend the stratified model of probabilistic processes to obtain a very general notion ofprocess priority. The main idea is to allow probability guards of value 0 to be associated with alternatives of a probabilistic summation expression. Such ...
Impossibility Results in the Equational Logic of Processes
This talk offers a survey of negative results on the existence of finite equational axiomatizations for bisimulation equivalence over fragments of algebraic process calculi.
Comments