An n! lower bound on formula size

DOI10.1145/772062.772064zbMATH Open1365.68270OpenAlexW2175748456MaRDI QIDQ5267432FDOQ5267432

Neil Immerman, Micah Adler

Publication date: 13 June 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/772062.772064

Recommendations

• Formula size games for modal logic and \(\mu\)-calculus
• scientific article; zbMATH DE number 1500644
• scientific article; zbMATH DE number 1136084
• The Succinctness of First-order Logic over Modal Logic via a Formula Size Game
• Games on Trees and Syntactical Complexity of Formulas

zbMATH Keywords

lower boundstemporal logicdescriptive complexity

Mathematics Subject Classification ID

Temporal logic (03B44) Descriptive complexity and finite models (68Q19)

Cited In (17)

• Expressive power and succinctness of the positive calculus of binary relations
• A purely model-theoretic proof of the exponential succinctness gap between CTL\(^{+}\) and CTL
• A Lower Bound for the Formula Size of Rational Functions
• Title not available (Why is that?)
• Game characterizations for the number of quantifiers
• Succinctness of cosafety fragments of LTL via combinatorial proof systems
• On the complexity of existential positive queries
• Average-case lower bounds for formula size
• Comparing the succinctness of monadic query languages over finite trees
• Games for succinctness of regular expressions
• On the succinctness of some modal logics
• Quasilinear-time Computation of Generic Modal Witnesses for Behavioural Inequivalence
• On FO 2 Quantifier Alternation over Words
• Relating description complexity to entropy
• The succinctness of the cover modality
• Games for Temporal Logics on Trees
• A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints

This page was built for publication: An \(n!\) lower bound on formula size

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