Showing 2024Show all
2 papers · 1 filter
cs.LO2024
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
Parallel Play Saves Quantifiers
Marco Carmosino, Ronald Fagin, Neil Immerman +4
The number of quantifiers needed to express first-order properties is captured by two-player combinatorial games called multi-structural (MS) games. We play these games on linear o…