wiki_research

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

downwards_closure_state_complexity (412B)

      1 # Downwards closure state complexity
      2 
      3 - [karandikar2014state]: transforming a [DFA] to a [DFA] for the set of [subwords] has [exponential] [lower_bound] (not trivial)
      4   - [lower_bound] on larger alphabet already in [okhotin2010state]
      5 - [downwards_closure_cfl_state_complexity]
      6 
      7 Up: [downwards_closure], [state_complexity]
      8 
      9 Aliases: downward closure state complexity
     10 
     11 See also: [upwards_closure_state_complexity]