wiki_research

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

downwards_closure_cfl_state_complexity (489B)

      1 # Downwards closure CFL state complexity
      2 
      3 We can construct [automata] recognizing the downwards closure of a [CFL]: cf [bachmeier2014finite].
      4 - As an [NFA], it can be done with an [exponential] set of [states], and there is also an [exponential] [lower_bound].
      5 - As a [DFA], it can be done with a [doubly_exponential] set of [states], and there is also a [doubly_exponential] [lower_bound]
      6 
      7 Up: [downwards_closure_state_complexity], [CFL]
      8 
      9 See also: [upwards_closure_cfl_state_complexity]