wiki_research

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

upwards_closure (631B)


      1 # Upwards closure
      2 
      3 For L a [formal_language], the *upwards closure* of L is the set of [words] w which are [supersequences] of a word of L
      4 
      5 For any [formal_language] L, the upwards closure is a [regular_language]: this uses [Higman's_lemma]
      6 
      7 The upwards closure is a [upwards_closed_language]: any [supersequence] of a [word] of the upwards closure is in the upwards closure
      8 
      9 - [upwards_closure_state_complexity]
     10   - [upwards_closure_cfl_state_complexity]
     11 
     12 See also: [language_upwards_closed], [downwards_closure]
     13 
     14 Up: [formal_language_operator], [closure_operation] on [supersequences]
     15 
     16 Aliases: upward closure, superword closure