Multi-structural games and beyond

DOI10.46298/LMCS-20(4:27)2024MaRDI QIDQ7034601zbMATH OpenFDO

Authors Marco L. Carmosino, Ronald Fagin, Neil Immerman, Phokion G. Kolaitis, Jonathan Lenchner, Rik Sengupta

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-20(4:27)2024

zbMATH Keywords

complexitygameslogic

Mathematics Subject Classification ID

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

Cites work

• An application of games to the completeness problem for formalized theories
• An Ehrenfeucht-Fraïssé game for \(\mathcal L_{\omega_1\omega}\)
• scientific article; zbMATH DE number 3115890 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• Infinitary logics and 0-1 laws
• Monadic generalized spectra
• Number of quantifiers is better than number of tape cells
• On monadic NP vs monadic co-NP
• On Moschovakis closure ordinals
• On the number of quantifiers as a complexity measure
• The Size of a Formula as a Measure of Complexity
• The succinctness of first-order logic on linear orders
• Upper and lower bounds for first order expressibility

This page was built for publication: Multi-structural games and beyond

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