Optimizing Proof-Search via Linearization for Gödel-Löb Logic with Tree-Hypersequents
Tim S. Lyon Omar Y. A. A. Taher · 2026
Read Optimizing Proof-Search via Linearization for Gödel-Löb Logic with Tree-Hypersequents by Tim S. Lyon Omar Y. A. A. Taher (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-03484.txt.
Description
Lyon and Taher speed up proof search for Gödel-Löb logic, known as GL. They work in CSGL, a tree-hypersequent system for that logic. Poggiolesi had asked for a syntactic decidability proof in that system. Maggesi and Perini Brogi had sought a PSPACE proof-search method there. Both open asks are answered here.
The method is called linearization. It builds just one branch of a proof and one branch of a tree sequent at a time. That avoids the exponential blowup of naive search. The resulting algorithm decides validity in PSPACE, matching the known hardness of GL. When search fails, fragments of tree sequents combine into finite counter-models. That device proves the algorithm correct. Every valid formula also gets a proof made only of line sequents. This links depth-first search to linear nested sequent systems.
Catalog record
| CREATOR | Tim S. Lyon Omar Y. A. A. Taher |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.03484