Pomset Logic as a Calculus of Directed Cographs
Christian Retoré · 1999
We give an abstract formulation of proof-structures and nets for pomset logic which is shown to be equivalent to the original one with links. Here a proof-structure is described as a directed R&B-cograph, that is an edge bicoloured graph, one colour being a perfect matching and the other being a directed cograph --- directed cographs are are a simple generalization of cographs and series-parallel orders. The proof-nets are the proof-structures such that any alternate elementary circuit contains a chord. This representation is even more compact than usual descriptions: the algebraic properties of the connectives, associativity and commutativity, are interpreted by equality, as well as the presence or not of final disjunctions (final par's). But the main advantage is that any directed R&B-cograph, without any further specification is a proof-structure. We then study a step by step invertible transformation from proof-structures with links to directed R&B-cograph which is shown to preser...