2 papers
cs.LO2024
Characterizing Data Dependencies Then and Now
Phokion G. Kolaitis, Andreas Pieris
Data dependencies are integrity constraints that the data of interest must obey. During the 1980s, Janos Makowsky made a number of contributions to the study of data dependencies;…
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…