Reproduce “A Cyclic Proof System for HFLN” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Mayuko Kori, Takeshi Tsukada, Naoki Kobayashi
A novel cyclic proof system is introduced for HFL$_{N}$, a higher-order logic incorporating natural numbers and alternating fixed-point operators. This system establishes a sound method for proving HFL$_{N}$ formulas, with its unique global trace condition shown to be decidable, providing a foundation for verifying higher-order programs.
Key insights
- Inductive reasoning can be achieved implicitly through cyclic proofs, which avoid explicit induction rules and can simplify proof automation.
- Handling higher-order predicates and alternating fixed-points in cyclic proofs requires a delicate global trace condition that tracks the 'significance' of fixed-point unfoldings along derivation paths.
- The decidability of such a complex global trace condition, critical for automation, can be established by leveraging established techniques from automata theory.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.