Paper Info
Title
An effective characterization of the alternation hierarchy in two-variable logic
Abstract
We give an algebraic characterization, based on the bilateral semidirect product of finite monoids, of the quantifier alternation hierarchy in two-variable first-order logic on finite words. As a consequence, we obtain a new proof that this hierarchy is strict. Moreover, by application of the theory of finite categories, we are able to make our characterization effective: that is, there is an algorithm for determining the exact quantifier alternation depth for a given language definable in two-variable logic.
Year
DOI
Venue
2012
10.1145/3149822
ACM Transactions on Computational Logic
Keywords
DocType
Volume
FO2,Quantifier Alternation,J,Pseudovarities,Identities
Conference
abs/1205.4802
Issue
ISSN
Citations 
4
1529-3785
5
PageRank 
References 
Authors
0.46
11
2
Name
Order
Citations
PageRank
Andreas Krebs1172.86
Howard Straubing252860.92