Skip to main content

A theory of encodings and expressiveness


Rob van Glabbeek


UNSW Sydney


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

    author           = {van Glabbeek, Rob},
    doi              = {\_10},
    editor           = {{Baier, Christel Baier and Dal Lago, Ugo}},
    month            = apr,
    date             = {2018-4-14},
    year             = {2018},
    keywords         = {Expressiveness; encodings; languages; translations; compositionality; semantic equivalences;
    title            = {{A} Theory of Encodings and Expressiveness},
    series           = {Lecture Notes in Computer Science},
    address          = {Thessaloniki, Greece},
    pages            = {183-202},
    volume           = {10803},
    booktitle        = {Proceedings of the  21st International Conference on Foundations of Software Science and
                        Computational Structures},
    paperurl         = {},
    publisher        = {Springer}