Trustworthy Systems

Musings on encodings and expressiveness

Authors

Rob van Glabbeek

NICTA

UNSW

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

BibTeX Entry

  @inproceedings{vanGlabbeek_12,
    address          = {Newcastle upon Tyne, United Kingdom},
    author           = {van Glabbeek, Robert},
    booktitle        = {Combined 19th International Workshop on Expressiveness in Concurrency and 9th Workshop on Structural
                        Operational Semantics},
    doi              = {10.4204/EPTCS.89.7},
    editor           = {{Bas Luttik and Michel Reniers}},
    keywords         = {system description languages, translations, encodings, expressiveness},
    month            = aug,
    pages            = {81---98},
    paperurl         = {https://trustworthy.systems/publications/nicta_full_text/6112.pdf},
    publisher        = {Open Publishing Association},
    title            = {Musings on Encodings and Expressiveness},
    year             = {2012}
  }

Download