First-Order Queries on Finite Abelian Groups

We study the computational problem of checking whether a logical sentence is true in a finite abelian group. We prove that model checking first-order sentences on finite abelian groups is fixed-parameter tractable, when parameterized by the size of the sentence. We also prove that model checking monadic second-order sentences on finite abelian groups finitely presented by integer matrices is not fixed-parameter tractable (under standard assumptions in parameterized complexity).

Authors

• Simone Bova
• Barnaby Martin

Keywords

• Finite Abelian Groups
• First-Order Logic
• Monadic Second-Order Logic