Paper: Guarded Negation Transitive Closure Logic (at LICS 2026)
Open access: https://doi.org/10.4230/LIPIcs.LICS.2026.43
Abstract
We study the guarded negation fragment of transitive closure logic (GNTC). We show that the satisfiability problem for GNTC is 2ExpTime-complete, by establishing the following reductions: (i) a polynomial-time reduction from the satisfiability problem for GNTC to the satisfiability problem for the unary negation fragment UNTC of GNTC, and (ii) a direct exponential-time reduction from the satisfiability problem for UNTC to the non-emptiness problem for 2-way alternating parity tree automata. Furthermore, we show that the model checking problem for GNTC is 𝖯^NP[𝒪(log² n)]-complete in combined complexity. Our result implies 𝖯^NP[𝒪(log² n)]-completeness for both UNTC and UNFO^reg, which were left open in previous works.
BibTeX
@InProceedings{FigueiraFigueiraNak-GuardedNegationTran,
author = {Diego Figueira and Santiago Figueira and Yoshiki Nakamura},
title = {Guarded Negation Transitive Closure Logic},
booktitle = {Proceedings of the Forty-First Annual Symposium on Logic in Computer Science (LICS 2026)},
year = {2026},
month = {July},
pages = {43:1--43:29},
location = {Lisbon, Portugal},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
doi = {10.4230/LIPIcs.LICS.2026.43}
}
