On the Length of Medial-Switch-Mix Derivations - Archive ouverte HAL Access content directly
Conference Papers Year : 2017

On the Length of Medial-Switch-Mix Derivations

(1) , (2)
1
2

Abstract

Switch and medial are two inference rules that play a central role in many deep inference proof systems. In specific proof systems, the mix rule may also be present. In this paper we show that the maximal length of a derivation using only the inference rules for switch, medial, and mix, modulo associativity and commutativity of the two binary con-nectives involved, is quadratic in the size of the formula at the conclusion of the derivation. This shows, at the same time, the termination of the rewrite system.
Fichier principal
Vignette du fichier
sm-length.pdf (279 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01635933 , version 1 (15-11-2017)

Identifiers

  • HAL Id : hal-01635933 , version 1

Cite

Paola Bruscoli, Lutz Strassburger. On the Length of Medial-Switch-Mix Derivations. WoLLIC 2017 - Logic, Language, Information, and Computation, Jul 2017, London, United Kingdom. ⟨hal-01635933⟩
117 View
73 Download

Share

Gmail Facebook Twitter LinkedIn More