Liberalized Variable Splitting

Roger Antonsen and Arild Waaler
Journal of Automated Reasoning, volume 38(1–3), pages 3–30, 2007.
@ARTICLE{AntonsenWaaler07,
  author =   {Roger Antonsen and Arild Waaler},
  title =    {Liberalized {V}ariable {S}plitting},
  journal =  {Journal of Automated Reasoning},
  year =     {2007},
  number =   {1–3},
  volume =   38,
  ee =       {http://dx.doi.org/10.1007/s10817-006-9055-9},
  pages =    {3–30}
}

Sammendrag

Variable splitting is a technique applicable to free variable tableaux, sequent calculi, and matrix characterizations that exploits a relationship between β- and γ-rules. Using contextual information to differentiate between occurrences of the same free variable in different branches, the technique admits conditions under which these occurrences may safely be assigned different values by substitutions. This article investigates a system of variable splitting and shows its consistency by a semantical argument. The splitting system is liberalized with respect to β-inferences analogously to a well-known liberalization of δ-rules, and this is used to show an exponential speedup compared to free variable systems without splitting.