A Logical Framework with Infinitary Terms

Abstract

Logical frameworks are successful in modeling proof systems. Recently, CoLF extended the logical framework LF to support higher-order rational terms that enable adequate encoding of circular objects and derivations. In this paper, we propose CoLF${}^{\omega }$ as an alternative interpretation of CoLF-style signatures where terms are taken to be all possibly infinitary terms that are consistent with a given signature. In particular, we propose the notion of productive Böhm trees, a particular kind of typed $\perp$-free Böhm trees that are closed under hereditary substitution. We show that the productive Böhm trees are capable of meta-encoding their own structure. Overall, we hope to establish CoLF${}^{\omega }$ as a new formal framework for the encoding of infinitary regular and non-regular structures.