First-Order Queries on Finite Abelian Groups

Authors Simone Bova, Barnaby Martin



PDF
Thumbnail PDF

File

LIPIcs.CSL.2015.41.pdf
  • Filesize: 0.51 MB
  • 19 pages

Document Identifiers

Author Details

Simone Bova
Barnaby Martin

Cite AsGet 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).
Keywords
  • Finite Abelian Groups
  • First-Order Logic
  • Monadic Second-Order Logic

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail