An n ! lower bound on formula size

DOI10.1145/772062.772064zbMath1365.68270OpenAlexW2175748456MaRDI QIDQ5267432

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

zbMATH Keywords

lower boundstemporal logicdescriptive complexity

Mathematics Subject Classification ID

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

Related Items (10)

Expressive power and succinctness of the positive calculus of binary relations ⋮ Quasilinear-time Computation of Generic Modal Witnesses for Behavioural Inequivalence ⋮ On FO 2 Quantifier Alternation over Words ⋮ On the succinctness of some modal logics ⋮ Unnamed Item ⋮ The succinctness of the cover modality ⋮ On the complexity of existential positive queries ⋮ Comparing the succinctness of monadic query languages over finite trees ⋮ A purely model-theoretic proof of the exponential succinctness gap between CTL\(^{+}\) and CTL ⋮ Games for Temporal Logics on Trees

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