wiki_research

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

monadic_second_order_logic (782B)

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