Linear Embedding for a Quantitative Comparison of Language Expressiveness

   page       BibTeX_logo.png   
Antonio Brogi, Alessandra Di Pierro, Herbert Wiklicky
QAPL'01, Quantitative Aspects of Programming Laguages (Satellite Event of PLI 2001), pages 207-237
Electronic Notes in Theoretical Computer Science 59(3)
2002

We introduce the notion of linear embedding which refines Shapiro's notion of embedding by recasting it in a linear-space based semantics setting. We use this notion to compare the expressiveness of a class of languages that employ asynchronous communication primitives à la Linda. The adoption of a linear semantics in which the observables of a language are linear operators (matrices) representing the programs transition graphs allows us to give quantitative estimates of the different expressive power of languages, thus improving previous results in the field.