Skip to main content

A theory of encodings and expressiveness

Authors

Rob van Glabbeek

DATA61

Abstract

This paper proposes a definition of what it means for one system description language to encode another one, thereby enabling an ordering of system description languages with respect to expressive power. I compare the proposed definition with other definitions of encoding and expressiveness found in the literature, and illustrate it on a well-known case study: the encoding of the synchronous in the asynchronous π-calculus.

BibTeX Entry

  @inproceedings{Glabbeek_18_2,
    publisher        = {Springer},
    doi              = {10.1007/978-3-319-89366-2\_10},
    series           = {LNCS 10803},
    booktitle        = {21st International Conference on Foundations of Software Science and Computation Structures (FoSSaCS
                        2018)},
    author           = {van Glabbeek, Rob},
    month            = apr,
    volume           = {10803},
    editor           = {{Baier, Christel Baier and Dal Lago, Ugo}},
    keywords         = {expressiveness; encodings; languages; translations; compositionality; semantic equivalences;
                        π-calculus.},
    year             = {2018},
    date             = {2018-4-14},
    title            = {{A} Theory of Encodings and Expressiveness},
    pages            = {183-202},
    address          = {Thessaloniki, Greece}
  }

Download

Served by Apache on Linux on seL4.