The CMSO transduction characterization of bounded shrub-depth
The CMSO transduction characterization of bounded shrub-depth
Let be a class of graphs, let denote counting monadic second-order logic with one free set-variable type, let be a transduction, and let denote the path on vertices. Transduction characterization conjecture. The class has bounded shrub-depth if and only if, for every transduction , there exists an integer such that
This conjecture proposes an asymptotic characterization of bounded shrub-depth through the transduction hierarchy: precisely the graph classes from which no counting monadic second-order transduction can produce paths of every length. The surrounding discussion presents it as plausible and does not give a resolution.
Sources & referencesView supporting material
Primary source
Robert Ganian, Petr Hliněný, Jaroslav Nešetřil, Jan Obdržálek and Patrice Ossona de Mendez, “Shrub-depth: Capturing Height of Dense Graphs”, arXiv:1707.00359 (2019).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.