Den Asynchronous π-calculus, föreslagna av Honda och Tokoro (1991) och, oberoende av, av Boudol (1992), är en delmängd av π-calculus (Milner et al., 1992) som innehåller inga uttryckliga operatörer för val och output-prefixering. Kommunikationsmekanismen i denna kalkyl, dock är tillräckligt kraftfull för att simulera output-prefixing, som visas av Honda och Tokoro (1991) och av Boudol (1992), och input-bevakat val, som visas av Nestmann och Pierce (2000). En naturlig fråga uppstår alltså om den är lika uttrycksfull som den fullständiga π-kalculus. Vi visar att så inte är fallet. Mer exakt visar vi att det inte finns någon enhetlig, fullständigt distribuerad översättning från π-calculus till den asynkrona π-calculus, upp till någon "rimlig" uppfattning om likvärdighet. Detta resultat är baserat på oförmågan hos asynkrona π-kalculus att bryta vissa symmetrier som eventuellt finns i den ursprungliga kommunikationskurvan. Med liknande argument bevisar vi en separation mellan π-calculus och CCS, och mellan π-calculus och π-calculus med intern rörlighet, en delmängd av π-calculus som föreslagits av Sangiorgi där de utgående åtgärderna endast kan överföra privata namn.
Till exempel i REF bevisar författaren att det inte finns någon rimlig kodning från π-calculus till den asynkrona π-calculus genom att visa att symmetrisk ledare val problem har ingen lösning i den asynkhrna versionen av π-calculus.
Comparing the Expressive Power of the Synchronous and the Asynchronous pi-calculi
{'venue': 'Mathematical Structures in Computer Science, 13(5) , 685-719, 2003', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}