Nie jesteś zalogowany | Zaloguj się

Definable decompositions for graphs of bounded linear clique width

Prelegent(ci)
Mikołaj Bojańczyk
Afiliacja
Uniwersytet Warszawski
Termin
15 marca 2017 14:15
Pokój
p. 5870
Seminarium
Seminarium „Teoria automatów”

We prove that for every positive integer k, there exists an mso1-transduction which inputs a graph of linear cliquewidth at most k and outputs, nondeterministically, some clique decomposition of the graph of width bounded by a function of k. A direct corollary of this result is the equivalence of the notions of cmso1-definability and recognizability on graphs of bounded linear cliquewidth.