Uniform Lyndon Interpolation via Non-wellfounded Proofs

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.

Authors

Institutions

Publication Details

Journal
Electronic Proceedings in Theoretical Computer Science
Published
2026-06-28
DOI
https://doi.org/10.4204/eptcs.447.40
Primary Topic
Polynomial and algebraic computation
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Uniform Lyndon Interpolation via Non-wellfounded Proofs

Thomas Studer, Borja Sierra Miranda
Electronic Proceedings in Theoretical Computer Science
Polynomial and algebraic computation
article

Uniform Lyndon Interpolation via Non-wellfounded Proofs

Thomas Studer, Borja Sierra Miranda
article en

Abstract

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.

Electronic Proceedings in Theoretical Computer ScienceVol. 447
University of Bern (CH)
National Science Foundation, Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
Openalex Percentile: Top 6%
Polynomial and algebraic computation
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.