On the number of quantifiers as a complexity measure

DOI10.4230/LIPICS.MFCS.2022.48MaRDI QIDQ6584049zbMATH OpenFDO

Authors Ronald Fagin, Jonathan Lenchner, Nikhil Vyas, Ryan Williams

Publication date 6 August 2024

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2022.48

zbMATH Keywords

\(s\)-\(t\) connectivitycomplexity measuremulti-structural gamesnumber of quantifiersrooted treestrees

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(7)

• Game characterizations for the number of quantifiers
• Succinctness of cosafety fragments of LTL via combinatorial proof systems
• Boolean basis, formula size, and number of modal operators
• From quantifier depth to quantifier number: separating structures with k variables
• Multi-structural games and beyond
• On the number of quantifiers needed to define Boolean functions
• Description complexity of unary structures in first-order logic with links to entropy

This page was built for publication: On the number of quantifiers as a complexity measure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6584049)