Search

• < Previous
• 1
• Next >

Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words

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&nbsp;[&hellip;]