Musings on Encodings and Expressiveness

• DOI: 10.4204/eptcs.89.7
• Publication Date: 2012-08-12T15:20:05Z
• Authors: Rob van Glabbeek
• Keywords: FOS: Computer and information sciences; Computer Science - Logic in Computer Science; QA75.5-76.95; 02 engineering and technology; 0102 computer and information sciences; 01 natural sciences; Logic in Computer Science (cs.LO); Electronic computers. Computer science; QA1-939; 0202 electrical engineering, electronic engineering, information engineering; F.1.2; Mathematics

In Proceedings EXPRESS/SOS 2012, arXiv:1208.2440<br/>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.<br/>