Uniform Lyndon Interpolation via Non-wellfounded Proofs

Borja Sierra Miranda
(University of Bern)
Thomas Studer
(University of Bern)

Non-wellfounded proof theory has been applied to establish uniform interpolation and Lyndon interpolation (separately) for multiple logics. However, it has not yet been used to prove uniform Lyndon interpolation. We close this gap by showing uniform Lyndon interpolation for the provability logic GLS. This logic was known to have uniform interpolation, but it was open whether it has uniform Lyndon interpolation (or at least non-uniform Lyndon interpolation). The methodology we provide is easy to adapt to other provability logics if a non-wellfounded sequent calculus is available for them. In addition, we offer an alternative proof of cut elimination for GLS via non-wellfounded proofs.

In Marta Bílková, Malvin Gattinger, Iris van der Giessen, Marianna Girlando and Yanjing Wang: Proceedings of the Sixteenth International Conference on Advances in Modal Logic (AiML 2026), Amsterdam, The Netherlands, 29-06-2026, Electronic Proceedings in Theoretical Computer Science 447, pp. 711–730.
Published: 29th June 2026.

ArXived at: https://dx.doi.org/10.4204/EPTCS.447.40 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org