An n! lower bound on formula size

DOI10.1145/772062.772064MaRDI QIDQ5267432zbMATH OpenOpenAlexFDO

Authors Micah Adler, Neil Immerman

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

zbMATH Keywords

lower boundstemporal logicdescriptive complexity

Mathematics Subject Classification ID

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

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

Cited in

(18)

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

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)