Chu spaces and their interpretation as concurrent objects | SpringerLink
Skip to main content
Springer Nature Link
Log in

Chu spaces and their interpretation as concurrent objects

  • Chapter
  • First Online:
Computer Science Today

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1000))

Abstract

A Chu space is a binary relation

from a set A to an antiset X defined as a set which transforms via converse functions. Chu spaces admit a great many interpretations by virtue of realizing all small concrete categories and most large ones arising in mathematical and computational practice. Of particular interest for computer science is their interpretation as computational processes, which takes A to be a schedule of events distributed in time, X to be an automaton of states forming an information system in the sense of Scott, and the pairs (a, x) in the

relation to be the individual transcriptions of the making of history. The traditional homogeneous binary relations of transition on X and precedence on A are recovered as respectively the right and left residuals of the heterogeneous binary relation

with itself. The natural algebra of Chu spaces is that of linear logic, made a process algebra by the process interpretation.

This work was supported by ONR under grant number N00014-92-J-1974.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. A. Asperti. A logic for concurrency. Manuscript, November 1987.

    Google Scholar 

  2. M. Barr. * -Autonomous categories, volume 752 of Lecture Notes in Mathematics. Springer-Verlag, 1979.

    Google Scholar 

  3. M. Barr. *-Autonomous categories and linear logic. Math Structures in Comp. Sci., 1(2):159–178, 1991.

    Google Scholar 

  4. C. Brown and D. Gurr. A categorical linear framework for Petri nets. In J. Mitchell, editor, Logic in Computer Science, pages 208–218. IEEE Computer Society, June 1990.

    Google Scholar 

  5. J.A. Bergstra and J.W. Klop. Process algebra for synchronous communication. Information and Control, 60:109–137, 1984.

    Article  Google Scholar 

  6. J.A. Bergstra and J.W. Klop. Process theory based on bisimulation semantics. In Proc. REX School/Workshop on Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, pages 50–122, Springer-Verlag, 1989.

    Google Scholar 

  7. R.T Casley, R.F. Crew, J. Meseguer, and V.R. Pratt. Temporal structures. Math. Structures in Comp. Sci., 1(2):179–213, July 1991.

    Google Scholar 

  8. C. A. Gunter and V. Gehlot. Nets as tensor theories. (preliminary report). In G. De Michelis, editor, Applications of Petri Nets, pages 174–191, 1989. Also Univ. of Pennsylvania, Logic and Computation Report Nr 17.

    Google Scholar 

  9. J.-Y. Girard. Linear logic. Theoretical Computer Science, 50:1–102, 1987.

    Article  Google Scholar 

  10. S. Gay and R. Nagarajan. A typed calculus of synchronous processes. In Logic in Computer Science, pages 210–220. IEEE Computer Society, June 1995.

    Google Scholar 

  11. V. Gupta and V.R. Pratt. Gates accept concurrent behavior. In Proc. 34th Ann. IEEE Symp. on Foundations of Comp. Sci., pages 62–71, 1993.

    Google Scholar 

  12. V. Gupta. Concurrent Kripke structures. In North American Process Algebra Workshop, Proceedings, Cornell CS-TR-93-1369, August 1993.

    Google Scholar 

  13. V. Gupta. Chu Spaces: A Model of Concurrency. PhD thesis, Stanford University, September 1994. Tech. Report, available as ftp://boole.stanford.edu/pub/gupthes.ps.Z.

    Google Scholar 

  14. C.A.R. Hoare. Communicating sequential processes. Communications of the ACM, 21(8):666–672, August 1978.

    Article  Google Scholar 

  15. P.T. Johnstone. Stone Spaces. Cambridge University Press, 1982.

    Google Scholar 

  16. G. Kahn. The semantics of a simple language for parallel programming. In Proc. IFIP Congress 74 North-Holland, Amsterdam, 1974.

    Google Scholar 

  17. G.M. Kelly. Basic Concepts of Enriched Category Theory, London Math. Soc. Lecture Notes. 64. Cambridge University Press, 1982.

    Google Scholar 

  18. Y. Lafont and T. Streicher. Games semantics for linear logic. In Proc. 6th Annual IEEE Symp. on Logic in Computer Science, pages 43–49, Amsterdam, July 1991.

    Google Scholar 

  19. R. Milner. Communication and Concurrency. Prentice-Hall, 1989.

    Google Scholar 

  20. R. Milner. Action calculi, or syntactic action structures. In MFCS'93, Proceedings, volume 711 of Lecture Notes in Computer Science, pages 105–121, Springer-Verlag, 1993.

    Google Scholar 

  21. R. Milner, J. Parrow, and D Walker. A calculus of mobile processes. Information and Control, 100:1–77, 1992.

    Google Scholar 

  22. M. Nielsen, G. Plotkin, and G. Winskel. Petri nets, event structures, and domains, part I. Theoretical Computer Science, 13:85–108, 1981.

    Article  Google Scholar 

  23. C.A. Petri. Fundamentals of a theory of asynchronous information flow. In Proc. IFIP Congress 62, pages 386–390, 1962. North-Holland, Amsterdam.

    Google Scholar 

  24. V.R. Pratt. Some constructions for order-theoretic models of concurrency. In Proc. Conf. on Logics of Programs, volume 193 of Lecture Notes in Computer Science, pages 269–283, Springer-Verlag, 1985.

    Google Scholar 

  25. V.R. Pratt. Modeling concurrency with partial orders. Int. J. of Parallel Programming, 15(1):33–71, February 1986.

    Article  Google Scholar 

  26. V.R. Pratt. The duality of time and information. In Proc. of CONCUR'92, volume 630 of Lecture Notes in Computer Science, pages 237–253, Springer-Verlag, 1992.

    Google Scholar 

  27. V.R. Pratt. The second calculus of binary relations. In MFCS'93, Proceedings, volume 711 of Lecture Notes in Computer Science, pages 142–155, Springer-Verlag, 1993.

    Google Scholar 

  28. V.R. Pratt. Chu spaces: Automata with quantum aspects. In Proc. Workshop on Physics and Computation (PhysCornp'94), Dallas, 1994. IEEE.

    Google Scholar 

  29. V.R. Pratt. Time and information in sequential and concurrent computation. In Proc. Theory and Practice of Parallel Programming (TPPP'94), Sendai, Japan, November 1994.

    Google Scholar 

  30. V.R. Pratt. Rational mechanics and natural mathematics. In TAPSOFT'95, volume 915 of Lecture Notes in Computer Science, pages 108–122, Springer-Verlag, 1995.

    Google Scholar 

  31. V.R. Pratt. The Stone gamut: A coordinatization of mathematics. In Logic in Computer Science, pages 444–454. IEEE Computer Society, June 1995.

    Google Scholar 

  32. H.A. Priestley. Representation of distributive lattices. Bull. London Math. Soc, 2:186–190, 1970.

    Google Scholar 

  33. K.I. Rosenthal. Quantales and their applications. Longman Scientific and Technical, 1990.

    Google Scholar 

  34. D. Scott. Data types as lattices. SIAM Journal on Computing, 5(3):522–587, 1976.

    Article  Google Scholar 

  35. R.A.G Seely. Linear logic, *-autonomous categories and cofree algebras. In Categories in Computer Science and Logic, volume 92 of Contemporary Mathematics, pages 371–382, held June 1987, Boulder, Colorado, 1989.

    Google Scholar 

  36. M. Stone. The theory of representations for Boolean algebras. Trans. Amer. Math. Soc, 40:37–111, 1936.

    MathSciNet  Google Scholar 

  37. B. Trakhtenbrot. Origins and metamorphoses of the trinity: logic, nets, automata. In D. Kozen, editor, Logic in Computer Science, pages 506–507. IEEE Computer Society, June 1995.

    Google Scholar 

  38. R. Van Glabbeek and G. Plotkin. Configuration structures. In Logic in Computer Science, pages 199–209. IEEE Computer Society, June 1995.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, Stanford University, 94305-2140, Stanford, CA

    Vaughan Pratt

Authors
  1. Vaughan Pratt
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Jan van Leeuwen

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Pratt, V. (1995). Chu spaces and their interpretation as concurrent objects. In: van Leeuwen, J. (eds) Computer Science Today. Lecture Notes in Computer Science, vol 1000. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0015256

Download citation

  • DOI: https://doi.org/10.1007/BFb0015256

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60105-0

  • Online ISBN: 978-3-540-49435-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics