The CMSO transduction characterization of bounded shrub-depth
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.