{"id":"arxiv/2610.18287","url":"https://arxiv.org/abs/2610.18287","tags":["cs.LO","math.LO"],"score":0,"title":"Finite-on-Top-of-Temporal CSPs in Fixed-Point Logic","domain":"cs.LO","source":"arxiv","authors":["Manuel Bodirsky","Philipp A. Grzywaczyk"],"reviews":0,"subject":"cs.LO","summary":"We study definability in fixed-point logic with counting (FPC) for a class of constraint satisfaction problems (CSPs) that simultaneously generalises finite-domain CSPs and temporal CSPs. The templates for the CSPs are first-order expansions of the structure $([k] \\times {\\mathbb Q};<_1,\\dots,<_k,\\sim)$ where $<_i \\, := \\{((i,x),(i,x')) \\mid x<x'\\}$ and $\\sim \\, := \\{((i,x),(i,x')) \\mid i \\in [k], x,x' \\in {\\mathbb Q}\\}$, i.e., $k$ copies of $({\\mathbb Q};<)$. Such a CSP is definable in FPC precisely when the template pp-constructs neither the ternary temporal relation $X$, which holds on…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-13","reactions":{}}