2026-08-14T23:53:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3254 2024-03-06T10:34:01Z ddc:004 open_access

Algebraic Characterization of the Alternation Hierarchy in FO^2[<] on Finite Words Straubing, Howard automata finite model theory 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Howard Straubing 2011 Is Part Of LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2011.525 urn:nbn:de:0030-drops-32549 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.525 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode