Abstract | ||
---|---|---|
We study multi-structural games, played on two sets ${\mathcal{A}}$ and ${\mathcal{B}}$ of structures. These games generalize Ehrenfeucht-Fraïssé games. Whereas Ehrenfeucht-Fraïssé games capture the quantifier rank of a first-order sentence, multi-structural games capture the number of quantifiers, in the sense that Spoiler wins the r-round game if and only if there is a first-order sentence ϕ wit... |
Year | DOI | Venue |
---|---|---|
2021 | 10.1109/LICS52264.2021.9470756 | 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) |
Keywords | DocType | ISBN |
Computer science,Lattices,Games,Size measurement,Complexity theory,Machinery | Conference | 978-1-6654-4895-6 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ronald Fagin | 1 | 8808 | 2643.66 |
Jonathan Lenchner | 2 | 129 | 14.84 |
Kenneth W. Regan | 3 | 0 | 0.34 |
Nikhil Vyas | 4 | 0 | 0.34 |