2 papers
cs.LO2025
On the Number of Quantifiers Needed to Define Boolean Functions
Marco Carmosino, Ronald Fagin, Neil Immerman +3
The number of quantifiers needed to express first-order (FO) properties is captured by two-player combinatorial games called multi-structural games. We analyze these games on binar…
cs.LO2024
Multi-Structural Games and Beyond
Marco Carmosino, Ronald Fagin, Neil Immerman +3
Multi-structural (MS) games are combinatorial games that capture the number of quantifiers of first-order sentences. On the face of their definition, MS games differ from Ehrenfeuc…