16.11. Kirstin Peters, TU Berlin: Über die Ausdrucksstärke des pi-Kalküls

Palamidessi bewies am Beispiel von Leader Election in symmetrischen Netzwerken, dass der pi-Kalkül mit mixed choice ausdrucksstärker ist als der pi-Kalkül mit separate choice. Der Beweis beruht auf der Tatsache, dass der pi-Kalkül mit mixed choice in der Lage ist, Symmetrien zu brechen, während das im pi-Kalkül mit separate choice nicht möglich ist.

Durch direktes Ausnutzen dieser Eigenschaft als Beispiel für die
unterschiedliche absolute Ausdrucksstärke der beiden Kalküle konnten wir einen einfacheren Beweis erstellen. Basierend auf diesem Ergebnis ergibt sich die Nichtexistenz einer Kodierung vom pi-Kalkül mit mixed choice in den pi-Kalkül mit separate choice mit homomorpher Übersetzung des Parallel-Operators unter verschiedenen Definitionen davon, was eine gute Kodierung ist, als einfache Folgerung.