Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
S. Bova, M. Barnaby:
"First-Order Queries on Finite Abelian Groups";
Vortrag: Annual Conference of the European Association for Computer Science Logic (CSL),
Berlin;
07.09.2015
- 10.09.2015; in: "Proceedings of the 24th EACSL Annual Conference on Computer Science Logic",
(2015),
ISSN: 1868-8969;
Paper-Nr. 57,
19 S.
Kurzfassung englisch:
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).
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.4230/LIPIcs.CSL.2015.41
Elektronische Version der Publikation:
http://publik.tuwien.ac.at/files/PubDat_247887.pdf
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.