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