wiki_research

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

second_order_logic (455B)

      1 # SO
      2 
      3 - [monadic_second_order_logic]
      4 - [descriptive_complexity]: correspondence with [polynomial_hierarchy]
      5   - [existential_second_order_logic] corresponds to [nptime], etc.,
      6     [quantifier_prefix]
      7 - [second_order_transitive_closure] SO(TC) [ferrarotti2018expressivity]
      8   - corresponds to [pspace]
      9   - can express [hamiltonian_cycle]
     10     - which is known not to be expressible in [monadic_second_order_logic]
     11 
     12 See also: [first_order_logic]
     13 
     14 Aliases: SO