An n ! lower bound on formula size
From MaRDI portal
Publication:5267432
DOI10.1145/772062.772064zbMath1365.68270MaRDI QIDQ5267432
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
Related Items
The succinctness of the cover modality, Comparing the succinctness of monadic query languages over finite trees, Quasilinear-time Computation of Generic Modal Witnesses for Behavioural Inequivalence, Unnamed Item, On the complexity of existential positive queries, On the succinctness of some modal logics, A purely model-theoretic proof of the exponential succinctness gap between CTL\(^{+}\) and CTL, Expressive power and succinctness of the positive calculus of binary relations, On FO 2 Quantifier Alternation over Words, Games for Temporal Logics on Trees