Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-27T11:24:28.376Z Has data issue: false hasContentIssue false
  • English
  • Français

Quantales, observational logic and process semantics

Published online by Cambridge University Press:  04 March 2009

Samson Abramsky  and
Steven Vickers
Samson Abramsky
Affiliation:
Department of Computing, Imperial College of Science, Technology and Medicine, 180 Queen's Gate, London, SW7 2BZ
Steven Vickers
Affiliation:
Department of Computing, Imperial College of Science, Technology and Medicine, 180 Queen's Gate, London, SW7 2BZ
Get access Rights & Permissions [Opens in a new window]

Abstract

Various notions of observing and testing processes are placed in a uniform algebraic framework in which observations are taken as constituting a quantale. General completeness criteria are stated, and proved in our applications.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 3 , Issue 2 , June 1993 , pp. 161 - 227
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abramsky, S. (1987a) Domain Theory and the Logic of Observable Properties, PhD Thesis, Queen Mary College, University of London.Google Scholar
Abramsky, S. (1987b) Observation equivalence as a testing equivalence. Theoretical Computer Science 53 225–241.CrossRefGoogle Scholar
Abramsky, S. (1991) Domain theory in logical form. Annals of Pure and Applied Logic 51 1–77.CrossRefGoogle Scholar
Abramsky, S. and Vickers, S. J. (1990) Quantales, Observational Logic and Process Semantics. Department of Computing Report DOC 90/1, Imperial College, London. (This earlier draft of the present paper contains significantly different treatments of some of the results.)Google Scholar
Baeten, J. C. M., Bergstra, J. A. and Klop, J. W. (1985) Ready trace semantics for concrete process algebra with priority operator. Report CS-R8517, Centrum voor Wiskunde en Informatica, Amsterdam.Google Scholar
Blamey, S. (1991) The soundness and completeness of axioms for CSP processes. In: Reed, G. M., Roscoe, A. W. and Wachter, R. F. (eds.), Topology and Category Theory in Computer Science, Oxford University Press, 29–56.CrossRefGoogle Scholar
Bloom, B., Istrail, S. and Meyer, A. (1988) Bisimulation can’t be traced, Preliminary Report. In: Proceedings 15th ACM Symposium on Principles of Programming Languages.CrossRefGoogle Scholar
Brookes, S. D., Hoare, C. A. R. and Roscoe, A. W. (1984) A theory of communicating sequential processes. JACM 31 (7) 560–599.CrossRefGoogle Scholar
Brookes, S. D. and Rounds, W. C. (1983) Behavioural equivalence relations induced by programming logics. In: Diaz, J. (ed.), Automata, Languages and Programming. Springer Lecture Notes in Computer Science 154 97–108.CrossRefGoogle Scholar
Conway, J. H. (1971) Regular Algebra and Finite Machines, Chapman and Hall, London.Google Scholar
DeNicola, R. and Hennessy, M. (1987) CCS without τs. In: Ehrig, , Kowalski, , Levi, and Montenari, (eds.), Tapsoft ’87. Springer Lecture Notes in Computer Science 249 138–152.Google Scholar
Dunn, J. M. (1986) Relevance Logic and Entailment. In: Gabbay, D. and Guenthner, F. (eds.), Handbook of Philosophical Logic III: Alternatives to Classical Logic, D. Reidel, Dordrecht117–224.CrossRefGoogle Scholar
Girard, J.-Y. (1987) Linear logic. Theoretical Computer Science 50 1–102.CrossRefGoogle Scholar
Girard, J.-Y. (1989a) Towards a geometry of interaction. In: Gray, J. W. and Scedrov, A. (eds.), Categories in Computer Science and Logic. Contemporary Mathematics 92, American Mathematical Society, 69–108.CrossRefGoogle Scholar
Girard, J.-Y. (1989b) Proofs and Types, translated with appendices by Lafont, Y. and Taylor, P. Cambridge Tracts in Theoretical Computer Science 7, Cambridge University Press.Google Scholar
Hennessy, M. (1988) Algebraic Theory of Processes, MIT Press, Cambridge, Massachusetts.Google Scholar
Hennessy, M. C. and Milner, A. J. R. G. (1985) Algebraic laws for non-determinism and concurrency. Journal of ACM 32 (1) 137–161.CrossRefGoogle Scholar
Hennessy, M. and Plotkin, G. (1987) Finite conjunctive non-determinism. In: Voss, K., Genrich, H.-J. and Rozenberg, G. (eds.), Concurrency and Nets, Springer-Verlag, 233–245.CrossRefGoogle Scholar
Hoare, C. A. R. (1985) Communicating Sequential Processes, Prentice-Hall International, Englewood Cliffs.Google Scholar
Hoare, C. A. R. and He, Jifeng (1987) The weakest prespecification. Information Processing Letters 24 127–132.CrossRefGoogle Scholar
Johnstone, P. T. (1982) Stone Spaces, Cambridge University Press, Cambridge.Google Scholar
Joyal, A. and Tierney, M. (1984) An Extension of the Galois Theory of Grothendieck. Memoirs of the American Mathematical Society 309.Google Scholar
Lafont, Y. (1988) The linear abstract machine. Theoretical Computer Science 59 157–180.CrossRefGoogle Scholar
Lambek, J. (1958) The mathematics of sentence structure. American Mathematical Monthly 65 (3) 154–170.CrossRefGoogle Scholar
Larsen, K. G. and Skou, A. (1989) Bisimulation through probabilistic testing. In: Proceedings 16th ACM Symposium on Principles of Programming Languages 344–352.Google Scholar
Mac Lane, S. (1971). Categories for the Working Mathematician, Springer-Verlag, New York.CrossRefGoogle Scholar
Milner, R. (1980) A Calculus of Communicating systems. Springer Lecture Notes in Computer Science 92. (Reprinted as Report ECS-LFCS-86–7, Computer Science Department, University of Edinburgh, 1986.)Google Scholar
Milner, R. (1989) Communication and Concurrency, Prentice-Hall International, Englewood Cliffs.Google Scholar
Mitchell, B. (1972) Rings with several objects. Advances in Mathematics 8 1–161.CrossRefGoogle Scholar
Mulvey, C. J. (1986) &. Supplemento ai Rendiconti del Circolo Matematico di Palermo, Serie II no. 12, 99–104.Google Scholar
Niefield, S. B. and Rosenthal, K. I. (1988) Constructing locales from quantales. Mathematical Proceedings of the Cambridge Philosophical Society 104 215–234.CrossRefGoogle Scholar
Olderog, E. and Hoare, C. A. R. (1986) Specification-oriented semantics for communicating processes. Acta Informatica 23 9–66.CrossRefGoogle Scholar
Park, D. M. R. (1981) Concurrency and Automata on Infinite Sequences. Springer Lecture Notes in Computer Science 104.CrossRefGoogle Scholar
Phillips, I. (1987) Refusal testing. Theoretical Computer Science 50 241–284.CrossRefGoogle Scholar
Pnueli, A. (1985). Linear and branching structures in the semantics and logics of reactive systems. Springer Lecture Notes in Computer Science 194 15–31.CrossRefGoogle Scholar
Rosenthal, K. I. (1990) Quantales and their Applications, Research Notes in Mathematics, Pitman, London.Google Scholar
Vickers, S. (1989) Topology via Logic, Cambridge University Press, Cambridge.Google Scholar
Ward, M. and Dilworth, R. P. (1939) Residuated lattices. Transactions of the American Mathematical Society 45 335–354.CrossRefGoogle Scholar