scientific article; zbMATH DE number 6678444

DOI10.4230/LIPICS.FSTTCS.2012.112MaRDI QIDQ2957485zbMATH OpenFDO

Authors Jakub Gajarský, Petr Hliněný

Publication date 26 January 2017

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2012.112

zbMATH Keywords

MSO graph propertyshrub-depthtree-depthtree-width

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Logic in computer science (03B70) Structural characterization of families of graphs (05C75) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Kernelizing MSO properties of trees of fixed height, and some consequences
• On the height of random m‐ary search trees
• Trees, grids, and MSO decidability: from graphs to matroids
• On the decidability of MSO+U on infinite trees
• scientific article; zbMATH DE number 4145923
• Random-tree Diameter and the Diameter-constrained MST
• Random-tree diameter and the diameter-constrained MST
• On Polynomial Time Constructions of Minimum Height Decision Tree
• scientific article; zbMATH DE number 6862107
• Optimizing tree decompositions in MSO

Cited in

(10)

• Width, depth, and space: tradeoffs between branching and dynamic programming
• When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)
• scientific article; zbMATH DE number 6862107 (Why is no real title available?)
• Climbing up the elementary complexity classes with theories of automatic structures
• Uniformly Automatic Classes of Finite Structures
• A finitary analogue of the downward Löwenheim-Skolem property
• Tree-depth, quantifier elimination, and quantifier rank
• Kernelizing MSO properties of trees of fixed height, and some consequences
• Bounding width on graph classes of constant diameter
• On low tree-depth decompositions

This page was built for publication:

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