{"id":"arxiv/2605.10841","url":"https://arxiv.org/abs/2605.10841","tags":["cs.LO","math.LO"],"score":0,"title":"Constant time testability of first-order logic with modulo counting on finitary graphs","domain":"cs.LO","source":"arxiv","authors":["Isolde Adler","Jenny Stimpson"],"reviews":0,"subject":"cs.LO","summary":"This paper studies algorithmic meta theorems for property testing with \\emph{constant running time} in the bounded degree model. In (Adler, Harwath 2018) it was shown that on graph classes $\\mathcal C^{w}_d$ consisting of all graphs with both degree at most $d$ and treewidth at most $w$, every problem expressible in monadic second-order logic with counting (CMSO) is testable with \\emph{polylogarithmic} running time (where $d,w\\in \\mathbb N$ are fixed). It was left open whether this can be improved to \\emph{constant} running time. In this paper we give a positive answer for testing CMSO on…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-11","reactions":{}}