Logic in Computer Science (LICS 2000)

Paper: Dominator Trees and Fast Verification of Proof Nets (at LICS 2000)

Authors: A.S. Murawski C.-H.L. Ong

Abstract

We consider the following decision problems: ProofNet: Given a multiplicative linear logic (MLL) proof structure, is it a proof net? EssNet: Given an essential net (of an intuitionistic MLL sequent), is it correct?In this paper, we show that linear-time algorithms for EssNet can be obtained by constructing the dominator tree of the input essential net. As a corollary, by showing that ProofNet is linear-time reducible to EssNet (by the trip translation), we obtain a linear-time algorithm for ProofNet. We show further that these linear-time algorithms can be optimized to simple one-pass algorithms - each node of the input structure is visited at most once. As another application of dominator trees, we obtain linear-time algorithms for the problems of sequentializing proof nets (i.e. given a proof net, find a derivation for the underlying MLL sequent) and essential nets.

BibTeX

  @InProceedings{MurawskiOng-DominatorTreesandFa,
    author = 	 {A.S. Murawski and C.-H.L. Ong},
    title = 	 {Dominator Trees and Fast Verification of Proof Nets},
    booktitle =  {Proceedings of the Fifteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2000},
    year =	 2000,
    editor =	 {Martin Abadi},
    month =	 {June}, 
    pages =      {181--191},
    location =   {Santa Barbara, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }