Co-Decompositions and FO Model Checking

Source: arxiv.org/abs/2611.04658

Benjamin Merlin Bumpus, Guilherme C. M. Gomes, Laura Larios-Jones, Will J. Turner

arXivarxiv/2611.04658Nov 3, 2026math.COscore 0

Tree decompositions describe large graphs as gluings of smaller component parts. Here we study their categorical duals, tree co-decompositions, which construct large graphs via fibered products of small constituent parts. Co-decompositions are compressed representations of graphs or relational structures: the decomposed object can be exponentially larger than the space required to specify the co-decomposition. Our main contribution is an algorithmic meta-theorem for first order logic: given only a co-decomposition of a $σ$-structure $G$ with $b$ bags, each of size at most $w$ and an FO…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.04658
curl -X POST /api/v1/records/arxiv/2611.04658/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.04658/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'