wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

courcelle_theorem (461B)

      1 # Courcelle theorem
      2 
      3 by [courcelle]
      4 
      5 Applies to [treelike_data]
      6 
      7 Also: bounded [cliquewidth] if we are given a witness of cliquewidth
      8 
      9 time f(|phi|, width) times linear in the graph
     10 
     11 [courcelle_logspace]
     12 
     13 The query dependency is [nonelementary], but for [FO] on [pathlike_data] it is [elementary], cf [lampis2026first]
     14 
     15 Up: [theorem] on [monadic_second_order_logic_model_checking], [algorithmic_metatheorem]
     16 
     17 Aliases: Courcelle's theorem
     18 
     19 See also: [treewidth]