The Power of Two Variables

on YouTube ↗25m

" summary

First-order logic with two variables over words is exactly captured by an algebraic condition on the syntactic monoid: definability is decidable by checking membership in the variety DA via explicit omega-equations. The two-variable fragment cannot express “two consecutive A’s” (the example language whose syntactic monoid has six elements fails the equation), the FO alternation hierarchy is infinite but collapses for any fixed alphabet size, and quantifier-depth for FO^2 is decidable by the sequence of equations U_n = V_n.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 1:05Some facts about FO[ ]
3. 2:25The algebraic decision procedure
4. 6:12Some facts about FO [ ]
5. 10:07Is the quantifier alternation depth hierarchy infinite?
6. 10:48Can one effectively determine the exact quantifier alternation depth of a language in FO [ ]?
7. 11:37System of equations for alternation depth
8. 14:25Strictness of the hierarchy follows from these equations
9. 17:40Adding a Successor Relation
10. 18:14Adding a Between Relation (Krebs, Lodaya, Pandya, Straubing)
11. 19:26Is the quantifier alternation depth (wrt FO[ ]) of languages in FO , bet bounded?
12. 20:18Is there an algebraic decision procedure for definability in FO , bet?
13. 22:14A Note on the Proofs
14. 23:01Limitations of this approach