loading...
A Proof Theory for Generic Judgments: An extended abstract
Ottawa, Canada June 22-June 25
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2003.121005118th Annual IEEE Symposium on Logic i ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Dale Miller, INRIA/Futurs/Saclay & ?cole polytechnique
Alwen Tiu, ?cole polytechnique & Penn State University
A powerful and declarative means of specifying computations containing abstractions involves meta-level, universally quantified generic judgments. We present a proof theory for such judgments in which signatures are associated to each sequent (used to account for eigenvariables of the sequent) and to each formula in the sequent (used to account for generic variables locally scoped over the formula). A new quantifier, \bigtriangledown, is introduced to explicitly manipulate the local signature. Intuitionistic logic extended with \bigtriangledown satisfies cut-elimination even when the logic is additionally strengthened with a proof theoretic notion of definitions. The resulting logic can be used to encode naturally a number of examples involving name abstractions, and we illustrate using the \pi-calculus and the encoding of object-level provability.
Index Terms:
proof search, reasoning about operational semantics, generic judgments, higher-order abstract syntax
Citation:
Dale Miller, Alwen Tiu, "A Proof Theory for Generic Judgments: An extended abstract," lics, pp.118, 18th Annual IEEE Symposium on Logic in Computer Science (LICS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.