Trustworthy Systems

A theory of encodings and expressiveness

Authors

Rob van Glabbeek

DATA61

UNSW Sydney

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{vanGlabbeek_18_2,
    address          = {Thessaloniki, Greece},
    author           = {van Glabbeek, Robert},
    booktitle        = {Proceedings of the  21st International Conference on Foundations of Software Science and
                        Computational Structures},
    date             = {2018-4-14},
    doi              = {https://doi.org/10.1007/978-3-319-89366-2\_10},
    editor           = {{Baier, Christel Baier and Dal Lago, Ugo}},
    keywords         = {Expressiveness; encodings; languages; translations; compositionality; semantic equivalences;
                        π-calculus.},
    month            = apr,
    pages            = {183-202},
    paperurl         = {https://trustworthy.systems/publications/csiro_full_text/vanGlabbeek_18_2.pdf},
    publisher        = {Springer},
    series           = {Lecture Notes in Computer Science},
    title            = {{A} Theory of Encodings and Expressiveness},
    volume           = {10803},
    year             = {2018}
  }

Download