Algebraic Characterization of the Alternation Hierarchy in FO^2[<] on Finite Words

Author Howard Straubing



PDF
Thumbnail PDF

File

LIPIcs.CSL.2011.525.pdf
  • Filesize: 403 kB
  • 13 pages

Document Identifiers

Author Details

Howard Straubing

Cite AsGet BibTex

Howard Straubing. Algebraic Characterization of the Alternation Hierarchy in FO^2[<] on Finite Words. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 525-537, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/LIPIcs.CSL.2011.525

Abstract

We give an algebraic characterization of the quantifier alternation hierarchy in first-order two-variable logic on finite words. As a result, we obtain a new proof that this hierarchy is strict. We also show that the first two levels of the hierarchy have decidable membership problems, and conjecture an algebraic decision procedure for the other levels.
Keywords
  • automata
  • finite model theory

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