Howe's method for higher-order languages

doi:10.1017/CBO9780511792588.006

5 - Howe's method for higher-order languages

Published online by Cambridge University Press: 05 November 2011

Andrew Pitts

Edited by

Davide Sangiorgi and

Jan Rutten

Show author details

Andrew Pitts: Affiliation:
University of Cambridge
Davide Sangiorgi: Affiliation:
University of Bologna, Italy
Jan Rutten: Affiliation:
Stichting Centrum voor Wiskunde en Informatica (CWI), Amsterdam

Book contents

Get access

Summary

A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.

Image of the first page of this content. For PDF version, please use the ‘Save PDF’ preceeding this image.'

Type: Chapter
Information: Advanced Topics in Bisimulation and Coinduction , pp. 197 - 232

DOI: https://doi.org/10.1017/CBO9780511792588.006 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2011

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

Book purchase

Temporarily unavailable

References

[Abr90] S., Abramsky. The lazy λ-calculus. In D.A., Turner, editor, Research Topics in Functional Programming, chapter 4, pages 65–117. Addison Wesley, 1990.

[Abr91] S., Abramsky. Domain theory in logical form. Annals of Pure and Applied Logic, 51:1–77, 1991.Google Scholar

[Bal98] M., Baldamus. Semantics and logic of higher-order processes: Characterizing late context bisimulation. PhD thesis, Fachbereich 13 – Informatik, Technishen Universität Berlin, 1998.

[CH07] K., Crary and R., Harper. Syntactic logical relations for polymorphic and recursive types. In L., Cardelli, M., Fiore, and G., Winskel, editors, Computation, Meaning and Logic, Articles dedicated to Gordon Plotkin, volume 172 of Electronic Notes in Theoretical Computer Science, pages 259–299. Elsevier, 2007.

[FH92] M., Felleisen and R., Hieb. The revised report on the syntactic theories of sequential control and state. Theoretical Computer Science, 103:235–271, 1992.Google Scholar

[FHJ98] W., Ferreira, M., Hennessy, and A., Jeffrey. A theory of weak bisimulation for core CML. Journal of Functional Programming, 8(5):447–491, 1998.Google Scholar

[GH05] J.C., Godskesen and T., Hildebrandt. Extending Howe's method to early bisimulations for typed mobile embedded resources with local names. In FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science 25th International Conference, Hyderabad, India, December 15–18, 2005. Proceedings, volume 3821 of Lecture Notes in Computer Science, pages 140–151. Springer, 2005.

[Gor95] A.D., Gordon. Bisimilarity as a theory of functional programming. In Eleventh Conference on the Mathematical Foundations of Programming Semantics, New Orleans, 1995, volume 1 of Electronic Notes in Theoretical Computer Science. Elsevier, 1995.

[Gor98] A.D., Gordon. Operational equivalences for untyped and polymorphic object calculi. In Gordon and Pitts [GP98], pages 9–54.

[GP98] A.D., Gordon and A.M., Pitts, editors. Higher Order Operational Techniques in Semantics. Cambridge University Press, 1998.

[How89] D.J., Howe. Equality in lazy computation systems. In 4th Annual Symposium on Logic inComputer Science, pages 198–203. IEEE Computer Society Press, 1989.

[How96] D.J., Howe. Proving congruence of bisimulation in functional programming languages. Information and Computation, 124(2):103–112, 1996.Google Scholar

[JR99] A., Jeffrey and J., Rathke. Towards a theory of bisimulation for local names. In 14th Annual Symposium on Logic in Computer Science, pages 56–66. IEEE Computer Society Press, 1999.

[JR00] A., Jeffrey and J., Rathke. A theory of bisimulation for a fragment of concurrent ML with local names. In Proceedings of the 15th Annual Symposium on Logic in Computer Science, pages 311–321. IEEE Computer Society Press, 2000.

[JR05] A., Jeffrey and J., Rathke. Contextual equivalence for higher-order π-calculus revisited. Logical Methods in Computer Science, 1:(1), April 2005.Google Scholar

[Las98a] S.B., Lassen. Relational reasoning about contexts. InGordon and Pitts [GP98], pages 91–135.

[Las98b] S.B., Lassen. Relational reasoning about functions and nondeterminism. PhD thesis, Department of Computer Science, University of Aarhus, 1998.

[Mil77] R., Milner. Fully abstract models of typed lambda-calculi. Theoretical Computer Science, 4:1–22, 1977.Google Scholar

[Mil89] R., Milner. Communication and Concurrency. Prentice Hall, 1989.

[Mor69] J., Morris. Lambda calculus models of programming languages. PhD thesis, MIT, 1969.

[MT91] I.A., Mason and C.L., Talcott. Equivalence in functional languageswith effects. Journal of Functional Programming, 1:287–327, 1991.Google Scholar

[MT92] I.A., Mason and C.L., Talcott. Inferring the equivalence of functional programs that mutate data. Theoretical Computer Science, 105:167–215, 1992.Google Scholar

[Pie02] B.C., Pierce. Types and Programming Languages. MIT Press, 2002.

[Pit97a] A.M., Pitts. A note on logical relations between semantics and syntax. Logic Journal of the Interest Group in Pure and Applied Logics, 5(4):589–601, 1997.Google Scholar

[Pit97b] A.M., Pitts. Operationally-based theories of program equivalence. In P., Dybjer and A.M., Pitts, editors, Semantics and Logics of Computation, Publications of the Newton Institute, pages 241–298. Cambridge University Press, 1997.

[Pit02] A.M., Pitts. Operational semantics and program equivalence. In G., Barthe, P., Dybjer, and J., Saraiva, editors, Applied Semantics, Advanced Lectures, volume 2395 of Lecture Notes in Computer Science, Tutorial, pages 378–412. Springer, 2002. International Summer School, APPSEM 2000, Caminha, Portugal, September 9–15, 2000.

[PR98] A.M., Pitts and J.R.X., Ross. Process calculus based upon evaluation to committed form. Theoretical Computer Science, 195:155–182, 1998.Google Scholar

[PS08] A.M., Pitts and M.R., Shinwell. Generative unbinding of names. Logical Methods in Computer Science, 4(1:4):1–33, 2008.Google Scholar

[San96] D., Sangiorgi. Bisimulation for higher-order process calculi. Information and Computation, 131(2):141–178, 1996.Google Scholar

[San12] D., Sangiorgi. An Introduction to Bisimulation and Coinduction. Cambridge University Press, 2012.

[SKS07] D., Sangiorgi, N., Kobayashi, and E., Sumii. Environmental bisimulations for higher-order languages. In Twenty-Second Annual IEEE Symposium on Logic In Computer Science (LICS'07), pages 293–302. IEEE Computer Society Press, July 2007.

[Sum09] E., Sumii. A complete characterization of observational equivalence in polymorphic lambda-calculus with general references. In Computer Science Logic, Proceedings of 18th EACSL Annual Conference (CSL 2009), volume 5771 of Lecture Notes in Computer Science, pages 455–469 Springer, 2009.

[Win93] G., Winskel. The Formal Semantics of Programming Languages. Foundations of Computing. The MIT Press, 1993.