APICe » Publications » LinearembeddingEntcs158

Linear Embedding for a Quantitative Comparison of Language Expressiveness

Antonio Brogi, Alessandra Di Pierro, Herbert Wiklicky
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.
Electronic Notes in Theoretical Computer Science 59(3), pages 207-237, 2002
Quantitative Aspects of Programming Languages (QAPL'01 @ PLI 2001)
@article{linearembedding-entcs158,
	Author = {Brogi, Antonio and Di Pierro, Alessandra  and Wiklicky, Herbert},
	Doi = {10.1016/S1571-0661(04)00289-0},
	Issn = {1571-0661},
	Journal = {Electronic Notes in Theoretical Computer Science},
	Note = {Quantitative Aspects of Programming Languages (QAPL'01 @ PLI 2001)},
	Number = 3,
	Pages = {207--237},
	Title = {Linear Embedding for a Quantitative Comparison of Language Expressiveness},
	Url = {http://www.sciencedirect.com/science/article/pii/S1571066104002890},
	Volume = 59,
	Year = 2002}