Matching in the Pi-Calculus

We study whether, in the pi-calculus, the match prefix—a conditional operator testing two names for (syntactic) equality—is expressible via the other operators. Previously, Carbone and Maffeis proved that matching is not expressible this way under rather strong requirements (preservation and reflect...

Full description

Saved in:
Bibliographic Details
Published in:Electronic proceedings in theoretical computer science 2014-08, Vol.160 (Proc. EXPRESS/SOS 2014), p.16-29
Main Authors: Peters, Kirstin, Yonova-Karbe, Tsvetelina, Nestmann, Uwe
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c257t-7f2a2a5e58b501a9b40207572044561c830367feda092bb6112b78d9471f2ecd3
container_end_page 29
container_issue Proc. EXPRESS/SOS 2014
container_start_page 16
container_title Electronic proceedings in theoretical computer science
container_volume 160
creator Peters, Kirstin
Yonova-Karbe, Tsvetelina
Nestmann, Uwe
description We study whether, in the pi-calculus, the match prefix—a conditional operator testing two names for (syntactic) equality—is expressible via the other operators. Previously, Carbone and Maffeis proved that matching is not expressible this way under rather strong requirements (preservation and reflection of observables). Later on, Gorla developed a by now widely-tested set of criteria for encodings that allows much more freedom (e.g. instead of direct translations of observables it allows comparison of calculi with respect to reachability of successful states). In this paper, we offer a considerably stronger separation result on the non-expressibility of matching using only Gorla's relaxed requirements.
doi_str_mv 10.4204/EPTCS.160.3
format article
fullrecord <record><control><sourceid>doaj_cross</sourceid><recordid>TN_cdi_doaj_primary_oai_doaj_org_article_1e4d6821543c44d9a5f54f061de9b8ba</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><doaj_id>oai_doaj_org_article_1e4d6821543c44d9a5f54f061de9b8ba</doaj_id><sourcerecordid>oai_doaj_org_article_1e4d6821543c44d9a5f54f061de9b8ba</sourcerecordid><originalsourceid>FETCH-LOGICAL-c257t-7f2a2a5e58b501a9b40207572044561c830367feda092bb6112b78d9471f2ecd3</originalsourceid><addsrcrecordid>eNpNkEtLw1AQRi-iYKlduXSTvSTe92MpoWqhYsG6vsx9tbfERpJ04b83bUWczQyzON_HQeiW4IpTzB_mq3X9XhGJK3aBJhQrUVKi8eW_-xrN-n6Hx2GGciMn6O4VBr_N-02R98WwjcUqlzU0_tAc-ht0laDp4-x3T9HH03xdv5TLt-dF_bgsPRVqKFWiQEFEoZ3ABIzj-Bioxk5cSOI1w0yqFANgQ52ThFCndDBckUSjD2yKFmduaGFnv7r8Cd23bSHb06PtNha6IfsmWhJ5kJoSwZnnPBgQSfCEJQnROO1gZN2fWb5r-76L6Y9HsD1qsidNdtRkGfsBwSFW7Q</addsrcrecordid><sourcetype>Open Website</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Matching in the Pi-Calculus</title><source>ROAD: Directory of Open Access Scholarly Resources</source><creator>Peters, Kirstin ; Yonova-Karbe, Tsvetelina ; Nestmann, Uwe</creator><creatorcontrib>Peters, Kirstin ; Yonova-Karbe, Tsvetelina ; Nestmann, Uwe</creatorcontrib><description>We study whether, in the pi-calculus, the match prefix—a conditional operator testing two names for (syntactic) equality—is expressible via the other operators. Previously, Carbone and Maffeis proved that matching is not expressible this way under rather strong requirements (preservation and reflection of observables). Later on, Gorla developed a by now widely-tested set of criteria for encodings that allows much more freedom (e.g. instead of direct translations of observables it allows comparison of calculi with respect to reachability of successful states). In this paper, we offer a considerably stronger separation result on the non-expressibility of matching using only Gorla's relaxed requirements.</description><identifier>ISSN: 2075-2180</identifier><identifier>EISSN: 2075-2180</identifier><identifier>DOI: 10.4204/EPTCS.160.3</identifier><language>eng</language><publisher>Open Publishing Association</publisher><ispartof>Electronic proceedings in theoretical computer science, 2014-08, Vol.160 (Proc. EXPRESS/SOS 2014), p.16-29</ispartof><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c257t-7f2a2a5e58b501a9b40207572044561c830367feda092bb6112b78d9471f2ecd3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Peters, Kirstin</creatorcontrib><creatorcontrib>Yonova-Karbe, Tsvetelina</creatorcontrib><creatorcontrib>Nestmann, Uwe</creatorcontrib><title>Matching in the Pi-Calculus</title><title>Electronic proceedings in theoretical computer science</title><description>We study whether, in the pi-calculus, the match prefix—a conditional operator testing two names for (syntactic) equality—is expressible via the other operators. Previously, Carbone and Maffeis proved that matching is not expressible this way under rather strong requirements (preservation and reflection of observables). Later on, Gorla developed a by now widely-tested set of criteria for encodings that allows much more freedom (e.g. instead of direct translations of observables it allows comparison of calculi with respect to reachability of successful states). In this paper, we offer a considerably stronger separation result on the non-expressibility of matching using only Gorla's relaxed requirements.</description><issn>2075-2180</issn><issn>2075-2180</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2014</creationdate><recordtype>article</recordtype><sourceid>DOA</sourceid><recordid>eNpNkEtLw1AQRi-iYKlduXSTvSTe92MpoWqhYsG6vsx9tbfERpJ04b83bUWczQyzON_HQeiW4IpTzB_mq3X9XhGJK3aBJhQrUVKi8eW_-xrN-n6Hx2GGciMn6O4VBr_N-02R98WwjcUqlzU0_tAc-ht0laDp4-x3T9HH03xdv5TLt-dF_bgsPRVqKFWiQEFEoZ3ABIzj-Bioxk5cSOI1w0yqFANgQ52ThFCndDBckUSjD2yKFmduaGFnv7r8Cd23bSHb06PtNha6IfsmWhJ5kJoSwZnnPBgQSfCEJQnROO1gZN2fWb5r-76L6Y9HsD1qsidNdtRkGfsBwSFW7Q</recordid><startdate>20140806</startdate><enddate>20140806</enddate><creator>Peters, Kirstin</creator><creator>Yonova-Karbe, Tsvetelina</creator><creator>Nestmann, Uwe</creator><general>Open Publishing Association</general><scope>AAYXX</scope><scope>CITATION</scope><scope>DOA</scope></search><sort><creationdate>20140806</creationdate><title>Matching in the Pi-Calculus</title><author>Peters, Kirstin ; Yonova-Karbe, Tsvetelina ; Nestmann, Uwe</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c257t-7f2a2a5e58b501a9b40207572044561c830367feda092bb6112b78d9471f2ecd3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2014</creationdate><toplevel>online_resources</toplevel><creatorcontrib>Peters, Kirstin</creatorcontrib><creatorcontrib>Yonova-Karbe, Tsvetelina</creatorcontrib><creatorcontrib>Nestmann, Uwe</creatorcontrib><collection>CrossRef</collection><collection>DOAJ Directory of Open Access Journals</collection><jtitle>Electronic proceedings in theoretical computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Peters, Kirstin</au><au>Yonova-Karbe, Tsvetelina</au><au>Nestmann, Uwe</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Matching in the Pi-Calculus</atitle><jtitle>Electronic proceedings in theoretical computer science</jtitle><date>2014-08-06</date><risdate>2014</risdate><volume>160</volume><issue>Proc. EXPRESS/SOS 2014</issue><spage>16</spage><epage>29</epage><pages>16-29</pages><issn>2075-2180</issn><eissn>2075-2180</eissn><abstract>We study whether, in the pi-calculus, the match prefix—a conditional operator testing two names for (syntactic) equality—is expressible via the other operators. Previously, Carbone and Maffeis proved that matching is not expressible this way under rather strong requirements (preservation and reflection of observables). Later on, Gorla developed a by now widely-tested set of criteria for encodings that allows much more freedom (e.g. instead of direct translations of observables it allows comparison of calculi with respect to reachability of successful states). In this paper, we offer a considerably stronger separation result on the non-expressibility of matching using only Gorla's relaxed requirements.</abstract><pub>Open Publishing Association</pub><doi>10.4204/EPTCS.160.3</doi><tpages>14</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 2075-2180
ispartof Electronic proceedings in theoretical computer science, 2014-08, Vol.160 (Proc. EXPRESS/SOS 2014), p.16-29
issn 2075-2180
2075-2180
language eng
recordid cdi_doaj_primary_oai_doaj_org_article_1e4d6821543c44d9a5f54f061de9b8ba
source ROAD: Directory of Open Access Scholarly Resources
title Matching in the Pi-Calculus
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-27T19%3A12%3A59IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-doaj_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Matching%20in%20the%20Pi-Calculus&rft.jtitle=Electronic%20proceedings%20in%20theoretical%20computer%20science&rft.au=Peters,%20Kirstin&rft.date=2014-08-06&rft.volume=160&rft.issue=Proc.%20EXPRESS/SOS%202014&rft.spage=16&rft.epage=29&rft.pages=16-29&rft.issn=2075-2180&rft.eissn=2075-2180&rft_id=info:doi/10.4204/EPTCS.160.3&rft_dat=%3Cdoaj_cross%3Eoai_doaj_org_article_1e4d6821543c44d9a5f54f061de9b8ba%3C/doaj_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c257t-7f2a2a5e58b501a9b40207572044561c830367feda092bb6112b78d9471f2ecd3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true