Structure Theorem and Strict Alternation Hierarchy for FO² on Words

Authors Philipp Weis, Neil Immerman



PDF
Thumbnail PDF

File

DagSemProc.06451.6.pdf
  • Filesize: 273 kB
  • 22 pages

Document Identifiers

Author Details

Philipp Weis
Neil Immerman

Cite AsGet BibTex

Philipp Weis and Neil Immerman. Structure Theorem and Strict Alternation Hierarchy for FO² on Words. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 6451, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
https://doi.org/10.4230/DagSemProc.06451.6

Abstract

It is well-known that every first-order property on words is expressible using at most three variables. The subclass of properties expressible with only two variables is also quite interesting and well-studied. We prove precise structure theorems that characterize the exact expressive power of first-order logic with two variables on words. Our results apply to FO$^2[<]$ and FO$^2[<,suc]$, the latter of which includes the binary successor relation in addition to the linear ordering on string positions. For both languages, our structure theorems show exactly what is expressible using a given quantifier depth, $n$, and using $m$ blocks of alternating quantifiers, for any $mleq n$. Using these characterizations, we prove, among other results, that there is a strict hierarchy of alternating quantifiers for both languages. The question whether there was such a hierarchy had been completely open since it was asked in [Etessami, Vardi, and Wilke 1997].
Keywords
  • Descriptive complexity
  • finite model theory
  • alternation hierarchy
  • Ehrenfeucht-Fraisse games

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