LIPIcs.CSL.2015.41.pdf
- Filesize: 0.51 MB
- 19 pages
Document
First-Order Queries on Finite Abelian Groups
Authors
-
Part of:
Volume:
24th EACSL Annual Conference on Computer Science Logic (CSL 2015)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computer Science Logic (CSL) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2015-09-07
Cite As Get BibTex
Simone Bova and Barnaby Martin. First-Order Queries on Finite Abelian Groups. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 41-59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.CSL.2015.41
Abstract
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).
Subject Classification
Keywords
- Finite Abelian Groups
- First-Order Logic
- Monadic Second-Order Logic
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads