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

(23)

• A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints
• Formula size games for modal logic and \(\mu\)-calculus
• 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
• From quantifier depth to quantifier number: separating structures with k variables
• A Lower Bound for the Formula Size of Rational Functions
• Multi-structural games and number of quantifiers
• Succinctness issues for \(\textsf{LTL}_{\textsf{f}}\) and safety and cosafety fragments of \textsf{LTL}
• 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
• Boolean basis, formula size, and number of modal operators
• On the succinctness of atoms of dependency
• Modal logic is more succinct iff bi-implication is available in some form
• On FO 2 Quantifier Alternation over Words
• Quasilinear-time Computation of Generic Modal Witnesses for Behavioural Inequivalence
• Relating description complexity to entropy
• The succinctness of the cover modality
• Games for Temporal Logics on Trees

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)