APICe » Publications » EmbeddingIc108

Embedding as a Tool for Language Comparison

Frank S. de Boer, Catiuscia Palamidessi
This paper addresses the problem of defining a formal tool to compare the expressive power of different concurrent constraint languages. We refine the notion of embedding by adding some "reasonable" conditions, suitable for concurrent frameworks. The new notion, called modular embedding, is used to define a preorder among these languages, representing different degrees of expressiveness. We show that this preorder is not trivial (i.e., it does not collapse into one equivalence class) by proving that Flat CP cannot be embedded into Flat GHC, and that Flat GHC cannot be embedded into a language without communication primitives in the guards, while the converses hold.
Information and Computation, pages 128-157, 1994
@article{embedding-ic108,
	Author = {de Boer, Frank S. and Palamidessi, Catiuscia},
	Doi = {10.1006/inco.1994.1004},
	Journal = {Information and Computation},
	Number = 1,
	Pages = {128--157},
	Title = {Embedding as a Tool for Language Comparison},
	Url = {http://www.sciencedirect.com/science/article/pii/S0890540184710042},
	Volume = 108,
	Year = 1994}