An open logical framework
File(s)main.pdf (636.28 KB)
Accepted version
Author(s)
Honsell, F
Lenisa, M
Scagnetto, I
Liquori, L
Maksimovic, P
Type
Journal Article
Abstract
The LFP Framework is an extension of the Harper–Honsell–Plotkin’s Edinburgh Logical Framework LF with external
predicates, hence the name Open Logical Framework. This is accomplished by defining lock type constructors, which are a
sort of -modality constructors, releasing their argument under the condition that a possibly external predicate is satisfied
on an appropriate typed judgement. Lock types are defined using the standard pattern of constructive type theory, i.e. via
introduction, elimination and equality rules. Using LFP , one can factor out the complexity of encoding specific features of
logical systems, which would otherwise be awkwardly encoded in LF, e.g. side-conditions in the application of rules in Modal
Logics, and sub-structural rules, as in non-commutative Linear Logic. The idea of LFP is that these conditions need only
to be specified, while their verification can be delegated to an external proof engine, in the style of the Poincaré Principle
or Deduction Modulo. Indeed such paradigms can be adequately formalized in LFP . We investigate and characterize the
meta-theoretical properties of the calculus underpinning LFP : strong normalization, confluence and subject reduction. This
latter property holds under the assumption that the predicates are well-behaved, i.e. closed under weakening, permutation,
substitution and reduction in the arguments. Moreover, we provide a canonical presentation of LFP , based on a suitable
extension of the notion of βη-long normal form, allowing for smooth formulations of adequacy statements.
predicates, hence the name Open Logical Framework. This is accomplished by defining lock type constructors, which are a
sort of -modality constructors, releasing their argument under the condition that a possibly external predicate is satisfied
on an appropriate typed judgement. Lock types are defined using the standard pattern of constructive type theory, i.e. via
introduction, elimination and equality rules. Using LFP , one can factor out the complexity of encoding specific features of
logical systems, which would otherwise be awkwardly encoded in LF, e.g. side-conditions in the application of rules in Modal
Logics, and sub-structural rules, as in non-commutative Linear Logic. The idea of LFP is that these conditions need only
to be specified, while their verification can be delegated to an external proof engine, in the style of the Poincaré Principle
or Deduction Modulo. Indeed such paradigms can be adequately formalized in LFP . We investigate and characterize the
meta-theoretical properties of the calculus underpinning LFP : strong normalization, confluence and subject reduction. This
latter property holds under the assumption that the predicates are well-behaved, i.e. closed under weakening, permutation,
substitution and reduction in the arguments. Moreover, we provide a canonical presentation of LFP , based on a suitable
extension of the notion of βη-long normal form, allowing for smooth formulations of adequacy statements.
Date Issued
2013-07-31
Date Acceptance
2012-08-31
Citation
Journal of Logic and Computation, 2013, 26 (1), pp.293-335
ISSN
0955-792X
Publisher
Oxford University Press (OUP)
Start Page
293
End Page
335
Journal / Book Title
Journal of Logic and Computation
Volume
26
Issue
1
Copyright Statement
This is a pre-copyedited, author-produced PDF of an article accepted for publication in Journal of Logic and Computation following peer review. The version of record Furio Honsell, Marina Lenisa, Ivan Scagnetto, Luigi Liquori, and Petar Maksimovic
An open logical framework
J Logic Computation (2016) 26 (1): 293-335 is available online at: https://dx.doi.org/10.1093/logcom/ext028
An open logical framework
J Logic Computation (2016) 26 (1): 293-335 is available online at: https://dx.doi.org/10.1093/logcom/ext028
Subjects
Computation Theory & Mathematics
01 Mathematical Sciences
08 Information And Computing Sciences
22 Philosophy And Religious Studies
Publication Status
Published