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

CREATORTim S. Lyon Omar Y. A. A. Taher
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.03484

Browse the full library · About the Tower of Babel