Game characterizations for the number of quantifiers

DOI10.1017/S0960129523000415MaRDI QIDQ6620026zbMATH OpenFDO

Authors Lauri Hella, Kerkko Luosto

Publication date 16 October 2024

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0960129523000415

zbMATH Keywords

Ehrenfeucht-Fraïssé gamesformula-size gamesprenex normal formsemantic games

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• An n! lower bound on formula size
• An application of games to the completeness problem for formalized theories
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Die Widerspruchsfreiheit der allgemeinen Mengenlehre
• Formula size games for modal logic and \(\mu\)-calculus
• scientific article; zbMATH DE number 3885853 (Why is no real title available?)
• scientific article; zbMATH DE number 3528202 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• Number of quantifiers is better than number of tape cells
• On the number of quantifiers as a complexity measure
• Some exponential lower bounds on formula-size in modal logic
• 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: Game characterizations for the number of quantifiers

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