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