zbMATH — the first resource for mathematics

Embedding as a tool for language comparison. (English) Zbl 0788.68014
Summary: 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.

68N15 Theory of programming languages
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Full Text: DOI