Linear Embedding for a Quantitative Comparison of Language Expressiveness
Antonio Brogi, Alessandra Di Pierro, Herbert Wiklicky · Electronic Notes in Theoretical Computer Science · 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.