Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-08T05:54:15.502Z Has data issue: false hasContentIssue false

Two-dimensional proof-structures and the exchange rule

Published online by Cambridge University Press:  03 February 2004

CHRISTOPHE GAUBERT
Affiliation:
CNRS – FRUMAM, Institut de Mathématiques de Luminy, 163, avenue de Luminy – case 907, 13288 Marseille cedex 09, France Email: gaubert@iml.univ-mrs.fr
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In the paper Métayer (2001), Métayer transforms multiplicative proof-structures into orientable surfaces with boundaries. He investigates the link between the topological complexity and the number of exchanges in a sequentialisation. The theorem he achieves is about a particular rule of exchange (transpositions by blocks). We complete his approach by showing that the topological complexity does not provide any information in other cases (arbitrary exchange, upper bound of the number of exchanges). Then, we show that, on the other hand, the surface associated to a proof-structure is the surface of minimal complexity on which the proof can be drawn without crossing and respecting the local orientation.

Information

Type
Paper
Copyright
2004 Cambridge University Press