wiki_research

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

monadic_second_order_logic (813B)

      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 
     16 [Computational_complexity]:
     17 
     18 - Tractable on [trees]
     19   - Corresponds to [regular_tree_languages], cf [buchis_theorem]
     20 - Tractable on [treelike_data]
     21   - cf [Courcelle's_theorem]
     22   - it is [FPT] when parameterized by the [treewidth] of the graph and the [logical_formula]
     23 - [MSO1] [NP_hard] in [data_complexity] already on [planar_graphs]
     24 
     25 Up: [logic]
     26 
     27 See also: [tree_automaton], [courcelle_theorem], [first_order_logic], [second_order_logic], [monadic]
     28 
     29 Aliases: MSO, MSOL, monadic second order