Talks and Poster Presentations (with Proceedings-Entry):
S. Bova, M. Barnaby:
"First-Order Queries on Finite Abelian Groups";
Talk: Annual Conference of the European Association for Computer Science Logic (CSL),
- 2015-09-10; in: "Proceedings of the 24th EACSL Annual Conference on Computer Science Logic",
Paper ID 57,
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).
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.