Skip to main content

A theory of encodings and expressiveness


Rob van Glabbeek



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

    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
    author           = {van Glabbeek, Rob},
    month            = apr,
    volume           = {10803},
    editor           = {{Baier, Christel Baier and Dal Lago, Ugo}},
    keywords         = {expressiveness; encodings; languages; translations; compositionality; semantic equivalences;
    year             = {2018},
    date             = {2018-4-14},
    title            = {{A} Theory of Encodings and Expressiveness},
    pages            = {183-202},
    address          = {Thessaloniki, Greece}


Served by Apache on Linux on seL4.