Tree-depth, quantifier elimination, and quantifier rank

DOI10.1145/3209108.3209160MaRDI QIDQ5145295zbMATH OpenOpenAlexFDO

Authors Yijia Chen, Jörg Flum

Publication date 20 January 2021

Published in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3209108.3209160

Mathematics Subject Classification ID

Quantifier elimination, model completeness, and related topics (03C10) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• scientific article; zbMATH DE number 6678444
• When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)
• Counting bounded tree depth homomorphisms
• Tree-Width for First Order Formulae
• Where first-order and monadic second-order logic coincide

Cited in

(11)

• Tree-width for first order formulae
• When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)
• The classification of all quantifier-eliminable directed or undirected trees with a root
• The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem
• Cardinality Quantifiers in MLO over Trees
• The parameterized space complexity of model-checking bounded variable first-order logic
• Parameterized Parallel Computing and First-Order Logic
• On the descriptive complexity of color coding
• Counting bounded tree depth homomorphisms
• Kernelizing MSO properties of trees of fixed height, and some consequences
• On algorithms based on finitely many homomorphism counts

This page was built for publication: Tree-depth, quantifier elimination, and quantifier rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145295)