wiki_research

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

downwards_closure (792B)

      1 # Downwards closure
      2 
      3 For L a [formal_language], the *downwards closure* of L is the set of [words] w which are [subsequences] of a word of L
      4 
      5 For any [formal_language] L, the downwards closure is a [regular_language]: this uses [Higman's_lemma]
      6 
      7 The downwards closure is a [downwards_closed_language]: any [subsequence] of a [word] of the downwards closure is in the downwards closure
      8 
      9 Given an [NFA], we can build in [linear_time] an [NFA] recognizing the upwards closure: cf [bachmeier2014finite] Lemma 8.
     10 - this automaton is [weakly_acyclic_automaton]
     11 
     12 [downwards_closure_state_complexity]
     13 - [downwards_closure_cfl_state_complexity]
     14 
     15 See also: [language_downwards_closed], [upwards_closure]
     16 
     17 Up: [formal_language_operator], [closure_operation] on [subsequences]
     18 
     19 Aliases: downward closure