Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the Decidability of Process Equivalences for the pi-calculus
RISE - Research Institutes of Sweden, ICT, SICS.
1994 (English)Report (Other academic)
Abstract [en]

We present general results for showing process equivalences applied to the finite control fragment of the pi-calculus decidable. Firstly a Finite Reachability Theorem states that up to finite name spaces and up to a static normalisation procedure, the set of reachable agent expressions is finite. Secondly a Boundedness Lemma shows that no potential computations are missed when name spaces are chosen large enough, but finite. We show how these results lead to decidability for a number of pi-calculus equivalences such as strong or weak, late or early bismulation equivalence. Furthermore, for strong late equivalence we show how our techniques can be used to adapt the well-known Paige-Tarjan algorithm. Strikingly this results in a single exponential running time not much worse than the running time for the case of for instance CCS. Our results considerably strengthens previous results on decidable equivalences for parameter-passing process calculi.

Place, publisher, year, edition, pages
Swedish Institute of Computer Science , 1994, 1. , p. 18
Series
SICS Research Report, ISSN 0283-3638 ; R94:20
Keywords [en]
Program Verification, Mobile Processes, Process Equivalence, Bisimulation Equivalence
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:ri:diva-21391OAI: oai:DiVA.org:ri-21391DiVA, id: diva2:1041427
Available from: 2016-10-31 Created: 2016-10-31 Last updated: 2018-02-02Bibliographically approved

Open Access in DiVA

fulltext(1765 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 1765 kBChecksum SHA-512
6eea05a09b87226bb6946168b8cc982d0ec4845319f374f219dbf82aba8490aaa55f0ec529fea2116556127388a4243738b33ba231ed4b87d86ebb0ce081f00b
Type fulltextMimetype application/pdf

By organisation
SICS
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 5 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
v. 2.35.4