An n! lower bound on formula size
From MaRDI portal
Recommendations
Cited in
(25)- 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
- Description complexity of unary structures in first-order logic with links to entropy
- Exponential lower bounds on definable fixed points
- 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)
