Multi-structural games and number of quantifiers

DOI10.46298/LMCS-21(1:10)2025MaRDI QIDQ7034348zbMATH OpenFDO

Authors Ronald Fagin, Jonathan Lenchner, Kenneth W. Regan, Nikhil Vyas

Publication date 31 January 2025

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/LMCS-21(1:10)2025

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites work

• An n! lower bound on formula size
• An application of games to the completeness problem for formalized theories
• An Ehrenfeucht-Fraïssé class game
• Finite-model theory -- A personal perspective
• Formula size games for modal logic and \(\mu\)-calculus
• scientific article; zbMATH DE number 3115890 (Why is no real title available?)
• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• Monadic generalized spectra
• Number of quantifiers is better than number of tape cells
• On monadic NP vs monadic co-NP
• On the first-order prefix hierarchy
• Reachability is harder for directed than for undirected finite graphs
• The Size of a Formula as a Measure of Complexity
• The succinctness of first-order logic on linear orders

This page was built for publication: Multi-structural games and number of quantifiers

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