Skip to main content
SpringerLink
Log in
Book cover

International Conference on Concurrency Theory

CONCUR 1992: CONCUR '92 pp 237–253Cite as

The duality of time and information

  • Conference paper
  • First Online:

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

Abstract

The states of a computing system bear information and change time, while its events bear time and change information. We develop a primitive algebraic model of this duality of time and information for rigid local computation, or straightline code, in the absence of choice and concurrency, where time and information are linearly ordered. This shows the duality of computation to be more fundamental than the logic of computation for which choice is disjunction and concurrency conjunction.

To accommodate flexible distributed computing systems we then bring in choice and concurrency and pass to partially ordered time and information, the formal basis for this extension being Birkhoff-Stone dualtiy. A degree of freedom in how this is done permits a perfectly symmetric logic of computation amounting to Girard 's full linear logic, which we view as the natural logic of computation when equal importance is attached to choice and concurrency.

We conclude with an assessment of the prospects for extending the duality to other organizations of time and information besides partial orders in order to accommodate real time, nonmonotonic logic, and automata that can forget, and speculate on the philosophical significance of the duality.

This work was supported by the National Science Foundation under grant number CCR-8814921 and a gift from Mitsubishi.

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

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. G. Birkhoff. On the combination of subalgebras. Proc. Cambridge Phil. Soc, 29:441–464, 1933.

    Article  MATH  Google Scholar 

  2. 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.

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

  5. S.C. Kleene. Representation of events in nerve nets and finite automata. In Automata Studies, pages 3–42. Princeton University Press, Princeton, NJ, 1956.

    Google Scholar 

  6. Christian Kloesel, editor. Writings of Charles S. Peirce: A Chronological Edition, volume 4, 1879–1884. Indiana University Press, Bloomington, IN, 1986.

    Google Scholar 

  7. M. Nielsen, G. Plotkin, and G. Winskel. Petri nets, event structures, and domains, part I. Theoretical Computer Science, 13, 1981.

    Google Scholar 

  8. C. Papadimitriou. The Theory of Database Control. Computer Science Press, 1986.

    Google Scholar 

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

    Google Scholar 

  10. V.R. Pratt. Action logic and pure induction. In J. van Eijck, editor, Logics in AI: European Workshop JELIA '90, LNCS 478, pages 97–120, Amsterdam, NL, September 1990. Springer-Verlag.

    Google Scholar 

  11. V.R. Pratt. Event spaces und their linear logic. In Proc. Second International Conference on Algebraic Methodology and Software Technology, Workshops in Computing, Iowa City, 1991. Springer-Verlag, to appear.

    Google Scholar 

  12. V.R. Pratt. Modcling concurrency with geometry. In Proc. 18th Ann. ACM Symposium on Principles of Programming Languages, pages 311–322, January 1991.

    Google Scholar 

  13. V.R. Pratt. Arithmetic + logic + geometry = concurrency. In Proc. First Latin American Symposium on Theoretical Informatics, LNCS 583, pages 430–447, São Paulo, Brazil, April 1992. Springer-Verlag.

    Google Scholar 

  14. V.R. Pratt. Origins of the calculus of binary relations. In Proc. 7th Annual IEEE Symp. on Logic in Computer Science, Santa Cruz, CA, June 1992.

    Google Scholar 

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

    MATH  MathSciNet  Google Scholar 

  16. W. Reisig. Petri Nets: An Introduction. Springer-Verlag, 1985.

    Google Scholar 

  17. M. Shields. Deterministic asynchronous automata. In E.J. Neuhold and G. Chroust, editors, Formal Models in Programming. Elsevier Science Publishers, B.V. (North Holland), 1985.

    Google Scholar 

  18. M. Stone. Topological representations of distributive lattices and brouwerian logics. Časopis Pěst. Math., 67:1–25, 1937.

    MATH  Google Scholar 

  19. G. Winskel. Event structures. In Petri Nets: Applications and Relationships to Other Models of Concurrency, Advances in Petri Nets 1986, LNCS 255, Bad-Honnef, September 1986. Springer-Verlag.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Stanford University, USA

    Vaughan R. Pratt

Authors
  1. Vaughan R. Pratt
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

W.R. Cleaveland

Rights and permissions

Reprints and permissions

Copyright information

© 1992 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Pratt, V.R. (1992). The duality of time and information. In: Cleaveland, W. (eds) CONCUR '92. CONCUR 1992. Lecture Notes in Computer Science, vol 630. Springer, Berlin, Heidelberg . https://doi.org/10.1007/BFb0084795

Download citation

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

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-55822-4

  • Online ISBN: 978-3-540-47293-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation