Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2014 | OriginalPaper | Buchkapitel

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

verfasst von : Davide Sangiorgi

Erschienen in: Coalgebraic Methods in Computer Science

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Nächstes Kapitel Generic Weakest Precondition Semantics from Monads Enriched with Order
Literatur
[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]
Ferreira, W., Hennessy, M., Jeffrey, A.: A theory of weak bisimulation for core CML. J. Funct. Program. 8(5), 447–491 (1998)MATHMathSciNetCrossRef
[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)
Metadaten
Titel
Higher-Order Languages: Bisimulation and Coinductive Equivalences (Extended Abstract)
verfasst von
Davide Sangiorgi
Copyright-Jahr
2014
Verlag
Springer Berlin Heidelberg
Buch
Coalgebraic Methods in Computer Science

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

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

Copyright-Jahr: 2014

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