Embedded Finite Models beyond Restricted Quantifier Collapse
From MaRDI portal
Abstract: 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.
This page was built for publication: Embedded Finite Models beyond Restricted Quantifier Collapse
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6433540)
