Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2014 | OriginalPaper | Chapter

Higher-Order Languages: Bisimulation and Coinductive Equivalences (Extended Abstract)

Author : Davide Sangiorgi

Published in: Coalgebraic Methods in Computer Science

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Higher-order languages have been widely studied in functional programming, following the \(\lambda \)-calculus. In a higher-order calculus, variables may be instantiated with terms of the language. When multiple occurrences of the variable exist, this mechanism results in the possibility of copying the terms of the language.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
next chapter Generic Weakest Precondition Semantics from Monads Enriched with Order
Literature
[Abr90]
Abramsky, S.: The lazy lambda calculus. In: Turner, D.A. (ed.) Research Topics in Functional Programming, pp. 65–117. Addison-Wesley, Reading (1990)
[ALS14]
Alberti, M., Lago, U.D., Sangiorgi, D.: On coinductive equivalences for higher-order probabilistic functional programs. In: Proceedings of POPL’14. ACM (2014)
[BSV14]
Bernardo, M., Sangiorgi, D., Vignudelli, V.: On the discriminating power of passivation and higher-order interaction, Submitted (2014)
[CRM03]
Comaniciu, D., Ramesh, V., Meer, P.: Kernel-based object tracking. IEEE Trans. Pattern Anal. Mach. Intell. 25(5), 564–577 (2003)CrossRef
[FHJ98]
[GAB+13]
Gordon, A.D., Aizatulin, M., Borgström, J., Claret, G., Graepel, T., Nori, A.V., Rajamani, S.K., Russo, C.V.: A model-learner pattern for bayesian reasoning. In: POPL, pp. 403–416 (2013)
[GH05a]
Godskesen, ChJ, Hildebrandt, T.: Extending Howe’s method to early bisimulations for typed mobile embedded resources with local names. In: Sarukkai, S., Sen, S. (eds.) FSTTCS 2005. LNCS, vol. 3821, pp. 140–151. Springer, Heidelberg (2005)
[GM84]
[Goo13]
Goodman, N.D.: The principles and practice of probabilistic programming. In: POPL, pp. 399–402 (2013)
[Gor93]
Gordon, A.D.: Functional programming and input/output. Ph.D. thesis, University of Cambridge (1993)
[GR96]
Gordon, A.D., Rees, G.D.: Bisimilarity for a first-order calculus of objects with subtyping. In: Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 386–395 (1996)
[How96]
[JP89]
Jones, C., Plotkin, G.D.: A probabilistic powerdomain of evaluations. In: LICS, pp. 186–195 (1989)
[JR99]
Jeffrey, A., Rathke, J.: Towards a theory of bisimulation for local names. In: 14th Annual IEEE Symposium on Logic in Computer Science, pp. 56–66 (1999)
[KH13]
Koutavas, V., Hennessy, M.: Symbolic bisimulation for a higher-order distributed language with passivation. In: D’Argenio, P.R., Melgratti, H. (eds.) CONCUR 2013 – Concurrency Theory. LNCS, vol. 8052, pp. 167–181. Springer, Heidelberg (2013) CrossRef
[KLS11]
Koutavas, V., Levy, P.B., Sumii, E.: From applicative to environmental bisimulation. Electr. Notes Theor. Comput. Sci. 276, 215–235 (2011)MathSciNetCrossRef
[KW06]
Koutavas, V., Wand, M.: Small bisimulations for reasoning about higher-order imperative programs. In: Proceedings of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 141–152 (2006)
[Las98]
Lassen, S.B.: Relational reasoning about functions and nondeterminism. Ph.D. thesis, Department of Computer Science, University of Aarhus (1998)
[LPSS11]
Lanese, I., Pérez, J.A., Sangiorgi, D., Schmitt, A.: On the expressiveness and decidability of higher-order process calculi. Inf. Comput. 209(2), 198–226 (2011)MATHCrossRef
[LSS09a]
Lenglet, S., Schmitt, A., Stefani, J.-B.: Howe’s method for calculi with passivation. In: Bravetti, M., Zavattaro, G. (eds.) CONCUR 2009. LNCS, vol. 5710, pp. 448–462. Springer, Heidelberg (2009) CrossRef
[LSS09b]
Lenglet, S., Schmitt, A., Stefani, J.-B.: Normal bisimulations in calculi with passivation. In: de Alfaro, L. (ed.) FOSSACS 2009. LNCS, vol. 5504, pp. 257–271. Springer, Heidelberg (2009) CrossRef
[LSS11]
Lenglet, S., Schmitt, A., Stefani, J.-B.: Characterizing contextual equivalence in calculi with passivation. Inf. Comput. 209(11), 1390–1433 (2011)MATHMathSciNetCrossRef
[Mil89]
Milner, R.: Communication and Concurrency. Prentice Hall, Upper Saddle River (1989)MATH
[Mor68]
Morris, J.H. Jr.: Lambda-calculus models of programming languages. Ph.D. thesis, Massachusetts Institute of Technology (1968)
[MS99]
Manning, C.D., Schütze, H.: Foundations of Statistical Natural Language Processing, vol. 999. MIT Press, Cambridge (1999)MATH
[Par81a]
Park, D.: A new equivalence notion for communicating systems. In: Maurer, G. (ed.) Bulletin EATCS, vol. 14, pp. 78–80 (1981). Abstract of the talk presented at the Second Workshop on the Semantics of Programming Languages, Bad Honnef, 16–20 March 1981. Abstracts collected in the Bulletin by B. Mayoh
[Par81b]
Park, D.: Concurrency and automata on infinite sequences. In: Deussen, P. (ed.) Theoretical Computer Science. LNCS, vol. 104, pp. 167–183. Springer, Heidelberg (1981) CrossRef
[Pea88]
Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Mateo (1988)
[Pfe01]
Pfeffer, A.: IBAL: a probabilistic rational programming language. In: IJCAI, pp. 733–740. Morgan Kaufmann (2001)
[Pit97]
Pitts, A.: Operationally-based theories of program equivalence. In: Pitts, A.M., Dybjer, P. (eds.) Semantics and Logics of Computation, pp. 241–298. Publications of the Newton Institute/Cambridge University Press, Cambridge (1997)CrossRef
[PPT08]
Park, S., Pfenning, F., Thrun, S.: A probabilistic language based on sampling functions. ACM Trans. Program. Lang. Syst. 31(1), 1–46 (2008)CrossRef
[PS12]
Piérard, A., Sumii, E.: A higher-order distributed calculus with name creation. In: LICS, pp. 531–540. IEEE (2012)
[RP02]
Ramsey, N., Pfeffer, A.: Stochastic lambda calculus and monads of probability distributions. In: POPL, pp. 154–165 (2002)
[San94]
[San98]
Sands, D.: Improvement theory and its applications. In: Gordon, A.D., Pitts, A.M. (eds.) Higher Order Operational Techniques in Semantics, pp. 275–306. Publications of the Newton Institute/Cambridge University Press, Cambridge (1998)
[San09]
Sangiorgi, D.: On the origins of bisimulation and coinduction. ACM Trans. Program. Lang. Syst. 31(4), 15:1–15:41 (2009)
[San12]
Sangiorgi, D.: Introduction to Bisimulation and Coinduction. Cambridge University Press, Cambridge (2012)MATH
[SKS07]
Sangiorgi, D., Kobayashi, N., Sumii, E.: Logical bisimulations and functional languages. In: Arbab, F., Sirjani, M. (eds.) FSEN 2007. LNCS, vol. 4767, pp. 364–379. Springer, Heidelberg (2007) CrossRef
[SKS11]
Sangiorgi, D., Kobayashi, N., Sumii, E.: Environmental bisimulations for higher-order languages. ACM Trans. Program. Lang. Syst. 33(1), 5 (2011)
[SP05]
Sumii, E., Pierce, B.C.: A bisimulation for type abstraction and recursion. In: Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 63–74 (2005)
[SS03]
Schmitt, A., Stefani, J.-B.: The m-calculus: a higher-order distributed process calculus. In: Proceedings POPL’03, pp. 50–61. ACM (2003)
[SW01]
Sangiorgi, D., Walker, D.: The Pi-Calculus - A Theory of Mobile Processes. Cambridge University Press, Cambridge (2001)MATH
[Thr02]
Thrun, S.: Robotic Mapping: A survey, pp. 1–35. Exploring Artificial Intelligence in the New Millennium, Schefferville (2002)
Metadata
Title
Higher-Order Languages: Bisimulation and Coinductive Equivalences (Extended Abstract)
Author
Davide Sangiorgi
Copyright Year
2014
Publisher
Springer Berlin Heidelberg
Book
Coalgebraic Methods in Computer Science

Print ISBN: 978-3-662-44123-7

Electronic ISBN: 978-3-662-44124-4

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-662-44124-4_1

Premium Partner

    Image Credits