wiki_research

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

monadic_second_order_logic (822B)

      1 # Monadic Second-Order Logic (MSO)
      2 
      3 Definition variants:
      4 
      5 - [monadic_second_order_logic_1]
      6   - [quantification] over [sets] of [vertices]
      7 - [monadic_second_order_logic_2]
      8   - [quantification] over [sets] of [edges]
      9 
     10 Extensions:
     11 
     12 - [counting_monadic_second_order_logic]
     13 - [weighted_MSO]
     14 - [guarded_second_order_logic]
     15 - [CMSO]
     16 
     17 [Computational_complexity]:
     18 
     19 - Tractable on [trees]
     20   - Corresponds to [regular_tree_languages], cf [buchis_theorem]
     21 - Tractable on [treelike_data]
     22   - cf [Courcelle's_theorem]
     23   - it is [FPT] when parameterized by the [treewidth] of the graph and the [logical_formula]
     24 - [MSO1] [NP_hard] in [data_complexity] already on [planar_graphs]
     25 
     26 Up: [logic]
     27 
     28 See also: [tree_automaton], [courcelle_theorem], [first_order_logic], [second_order_logic], [monadic]
     29 
     30 Aliases: MSO, MSOL, monadic second order