Tree-depth, quantifier elimination, and quantifier rank

DOI10.1145/3209108.3209160zbMATH Open1452.03086OpenAlexW2798639752MaRDI QIDQ5145295FDOQ5145295

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 (5)

• Cardinality Quantifiers in MLO over Trees
• 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
• Title not available (Why is that?)

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)