wiki_research

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

first_order_logic_regular_language (403B)

      1 # First order logic regular language
      2 
      3 On [word], [first_order_logic] corresponds to [star_free_language] and [monoid_aperiodic] by [schutzenbergers_theorem]
      4 
      5 connections to [fok]:
      6 - 3 variables suffice to express all first-order definable languages: [diekert2008survey]
      7 - [fo2] corresponds to [da]
      8   - connections to [unambiguous_polynomial]
      9 - [fo1] trivial
     10 
     11 Up: [first_order_logic], [regular_language]