Embedded Finite Models beyond Restricted Quantifier Collapse

04/18/2023
by   Michael Benedikt, et al.
0

We revisit evaluation of logical formulas that allow both uninterpreted relations, constrained to be finite, as well as interpreted vocabulary over an infinite domain: denoted in the past as embedded finite model theory. We extend the analysis of "collapse results": the ability to eliminate first-order quantifiers over the infinite domain in favor of quantification over the finite structure. We investigate several weakenings of collapse, one allowing higher-order quantification over the finite structure, another allowing expansion of the theory. We also provide results comparing collapse for unary signatures with general signatures, and new analyses of collapse for natural decidable theories.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset