Tree-depth, quantifier elimination, and quantifier rank

DOI10.1145/3209108.3209160zbMATH Open1452.03086OpenAlexW2798639752MaRDI QIDQ5145295FDOQ5145295

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

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

Mathematics Subject Classification ID

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

Cited In (10)

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

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)