Musings on Encodings and Expressiveness

Rob van Glabbeek
(NICTA)

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 case study: comparing the expressive power of CCS and CSP.

In Bas Luttik and Michel A. Reniers: Proceedings Combined 19th International Workshop on Expressiveness in Concurrency and 9th Workshop on Structured Operational Semantics (EXPRESS/SOS 2012), Newcastle upon Tyne, UK, September 3, 2012, Electronic Proceedings in Theoretical Computer Science 89, pp. 81–98.
Published: 12th August 2012.

ArXived at: http://dx.doi.org/10.4204/EPTCS.89.7 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org