Distinguishing and relating higher-order and first-order processes by expressiveness (Q1935453): Difference between revisions

This paper compares the expressive power of higher-order and first-order process calculi. To this end, the process-passing and the name-passing paradigms are formally related. It presents the following results: -- first-order pi-calculus can faithfully express basic higher-order pi-calculus, even when enriched with a relabelling operator; -- basic higher-order pi-calculus cannot interpret first-order pi-calculus reasonably; An encoding from first-order pi-calculus to basic higher-order pi-calculus enriched with a relabelling operator is also revisited and discussed.