3 papers
cs.LO2025
Who Wins the Multi-Structural Game?
Ronald Fagin, Neil Immerman, Phokion Kolaitis +2
Combinatorial games played between two players, called Spoiler and Duplicator, have often been used to capture syntactic properties of formal logical languages. For instance, the w…
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.IT2024
Breaking through the classical Shannon entropy limit: A new frontier through logical semantics
Luis A. Lastras, Barry M. Trager, Jonathan Lenchner +4
Information theory has provided foundations for the theories of several application areas critical for modern society, including communications, computer storage, and AI. A key asp…