Abstract:We prove the following results.
1, First order model checking is fixed-parameter tractable on the class of finite fields, as a corollary of results of Ax on the theory of (pseudo)finite fields.
2. Every hereditary graph class first order definable in the class of finite groups is monadically stable, and thus has fixed-parameter tractable first order model checking.
3. Monadic second order model checking is not slicewise polynomial on the class of cyclic groups of prime-power order, assuming E $\neq$ NE. Thus the same is true on the class of finite fields.
4. The class of finite fields is finitely axiomatizable in monadic second order logic, and so there are no pseudofinite fields in this setting.
From: Samuel Braunfeld [view email]
[v1]
Tue, 23 Jun 2026 18:51:17 UTC (13 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。