Mikołaj Bojańczyk ; Martin Grohe ; Michał Pilipczuk - Definable decompositions for graphs of bounded linear cliquewidth

lmcs:5295 - Logical Methods in Computer Science, January 25, 2021, Volume 17, Issue 1 - https://doi.org/10.23638/LMCS-17(1:5)2021
Definable decompositions for graphs of bounded linear cliquewidthArticle

Authors: Mikołaj Bojańczyk ; Martin Grohe ; Michał Pilipczuk ORCID

    We 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.

    https://doi.org/10.23638/LMCS-17(1:5)2021
    Source: arXiv.org:1803.05937
    Volume: Volume 17, Issue 1
    Published on: January 25, 2021
    Accepted on: November 16, 2020
    Submitted on: March 20, 2019
    Keywords: Computer Science - Logic in Computer Science
    Licence: Attribution 4.0 International (CC BY 4.0)
    Funding:
      Source : OpenAIRE Graph
    • A unified theory of finite-state recognisability; Funder: European Commission; Code: 683080

    1 Document citing this article

    Share and export

    Consultation statistics

    This page has been seen 1640 times.
    This article's PDF has been downloaded 375 times.