Article contents
Two-dimensional proof-structures and the exchange rule
Published online by Cambridge University Press: 03 February 2004
Abstract
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.
- Type
- Paper
- Information
- Copyright
- 2004 Cambridge University Press
- 5
- Cited by