Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Definable decompositions for graphs of bounded linear cliquewidth

Uproszczony widok
dc.abstract.enWe prove that for every positive integer k, there exists an MSO_1-transduction that given a graph of linear cliquewidth at most k outputs, nondeterministically, some cliquewidth 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 CMSO_1-definability and recognizability on graphs of bounded linear cliquewidth.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorGrohe, Martin
dc.contributor.authorPilipczuk, Michał
dc.contributor.authorBojańczyk, Mikołaj
dc.date.accessioned2024-01-24T21:19:17Z
dc.date.available2024-01-24T21:19:17Z
dc.date.issued2021
dc.description.financePublikacja bezkosztowa
dc.description.number1
dc.description.volume17
dc.identifier.doi10.23638/LMCS-17(1:5)2021
dc.identifier.issn1860-5974
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/104450
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofLogical Methods in Computer Science
dc.relation.pages1-40
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleDefinable decompositions for graphs of bounded linear cliquewidth
dc.typeJournalArticle
dspace.entity.typePublication