GPU-Accelerated Search and Certification of Bounded Indistinguishability in Finite Kripke Semantics

Abstract

We study finite Kripke semantics as an explicit search and certification problem for modal formulas. Sets of worlds are encoded as integer bitmasks, so Boolean connectives, $\square$, and $◊$ reduce to word-level containment and intersection tests. This gives a deterministic evaluator with an independent certificate checker, then scales it through a fused CUDA kernel for exhaustive small-frame scans. Over $K,T,S4,S5$, a corpus of 5,624 formulas is evaluated on all frames through five worlds, performing $1.63\times 10^{14}$ formula evaluations in 45 minutes on one H100. All 20,990 emitted countermodel certificates verify. In this bounded corpus, every $K$-refutable formula has a countermodel on at most two worlds, far below the standard filtration bound $2^{|\mathrm{Sub}(\phi )|}$. We then turn pairwise formula equivalence into a minimal-countermodel problem for biconditionals and synthesize semantic mirages: formulas that agree on every model up to a finite size and split only later. In particular, ${\alpha }_2=(\square ◊{)}^2\top$ and ${\alpha }_3=(\square ◊{)}^3\top$ agree on all frames of at most five worlds but are separated by a checked six-world path. Finally, we build a density-aggregated semantic atlas for representation-guided candidate retrieval and compare raw features, PCA, UMAP, spectral layouts, and random layouts under a common million-pair verifier budget. The result is a reproducible bridge between modal finite-model theory, GPU enumeration, certificate checking, and graphics-supported semantic exploration.

arXiv comment22 pages; ancillary files include code, data, 20,990 checked certificates, and rendering scripts