Lics

ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Forty-First Annual Symposium on

Logic in Computer Science (LICS 2026)

Paper: Guarded Negation Transitive Closure Logic (at LICS 2026)

Authors: Diego Figueira Santiago Figueira Yoshiki Nakamura

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}
  }
   

Last modified: 2026-09-2114:25
Sam Staton