Dominator trees and fast verification of proof nets

Andrzej S. Murawski, C.-h. Luke 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? The authors 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 sequentializing proof nets (i.e. given a proof net, find a derivation for the underlying MLL sequent) and essential nets.
BibTeX
@inproceedings{murawski2000dominator,
  author = {Andrzej S. Murawski and C.-H. Luke Ong},
  title = {{Dominator trees and fast verification of proof nets}},
  booktitle = {LICS},
  year = {2000},
  url = {https://openreview.net/forum?id=TPbD9RmmBJ},
}

Loading related content...

Figure