Distinguishing and relating higher-order and first-order processes by expressiveness
type: Item
instance of: scholarly article
title: Distinguishing and relating higher-order and first-order processes by expressiveness
zbMATH Open document ID: 1276.68129
author: Xian Xu
published in: Acta Informatica
publication date: 2013-02-15T00:00:00Z
review text: 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.
reviewed by: Jörg Desel
Mathematics Subject Classification ID: 68Q85
zbMATH DE Number: 6136726
zbMATH Keywords: pi-calculus
zbMATH Keywords: higher-order processes
zbMATH Keywords: first-order processes
MaRDI profile type: Publication
full work available at URL: s00236-012-0168-9
OpenAlex ID: W2075116711
cites work: Branching bisimilarity is an equivalence indeed!
cites work: A CPS encoding of name-passing in higher-order mobile embedded resources
cites work: Q4449170
cites work: Automata, Languages and Programming
cites work: The seal calculus
cites work: On quasi-open bisimulation
cites work: On the expressiveness of interaction
cites work: Towards a Unified Approach to Encodability and Separation Results for Process Calculi
cites work: On the expressiveness and decidability of higher-order process calculi
cites work: On the Expressiveness of Polyadic and Synchronous Communication in Higher-Order Process Calculi
cites work: Q3992568
cites work: Functions as processes
cites work: A calculus of mobile processes. I
cites work: Decoding choice encodings
cites work: Bisimulation for higher-order process calculi
cites work: \(\pi\)-calculus, internal mobility, and agent-passing calculi
cites work: A theory of bisimulation for the \(\pi\)-calculus
cites work: On the bisimulation proof method
cites work: Q4791841
cites work: The \(\pi\)-calculus: A theory of mobile processes
cites work: The m-calculus
cites work: Global Computing
cites work: Plain CHOCS. A second generation calculus for higher order processes
cites work: The linear time -- branching time spectrum. I: The semantics of concrete, sequential processes.
cites work: Branching Bisimilarity with Explicit Divergence
cites work: Branching time and abstraction in bisimulation semantics
cites work: On Bisimulation Theory in Linear Higher-Order π-Calculus
DOI: 10.1007/S00236-012-0168-9
description: scientific article; zbMATH DE number 6136726