License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2016.31
URN: urn:nbn:de:0030-drops-61759
Go to the corresponding LIPIcs Volume Portal

Horne, Ross ; Tiu, Alwen ; Aman, Bogdan ; Ciobanu, Gabriel

Private Names in Non-Commutative Logic

LIPIcs-CONCUR-2016-31.pdf (0.6 MB)


We present an expressive but decidable first-order system (named MAV1) defined by using the calculus of structures, a generalisation of the sequent calculus. In addition to first-order universal and existential quantifiers the system incorporates a de Morgan dual pair of nominal quantifiers called `new' and `wen', distinct from the self-dual Gabbay-Pitts and Miller-Tiu nominal quantifiers. The novelty of the operators `new' and `wen' is they are polarised in the sense that `new' distributes over positive operators while `wen' distributes over negative operators. This greater control of bookkeeping enables private names to be modelled in processes embedded as predicates in MAV1. Modelling processes as predicates in MAV1 has the advantage that linear implication defines a precongruence over processes that fully respects causality and branching. The transitivity of this precongruence is established by novel techniques for handling first-order quantifiers in the cut elimination proof.

BibTeX - Entry

  author =	{Ross Horne and Alwen Tiu and Bogdan Aman and Gabriel Ciobanu},
  title =	{{Private Names in Non-Commutative Logic}},
  booktitle =	{27th International Conference on Concurrency Theory (CONCUR 2016)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-017-0},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{59},
  editor =	{Jos{\'e}e Desharnais and Radha Jagadeesan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-61759},
  doi =		{10.4230/LIPIcs.CONCUR.2016.31},
  annote =	{Keywords: process calculi, calculus of structures, nominal logic, causal consistency}

Keywords: process calculi, calculus of structures, nominal logic, causal consistency
Collection: 27th International Conference on Concurrency Theory (CONCUR 2016)
Issue Date: 2016
Date of publication: 24.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI