wiki_research

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

language_upwards_closed (614B)

      1 # Language upwards closed
      2 
      3 A [formal_language] is *upwards closed* if any [subword] of the [formal_language] is in the [formal_language]
      4 
      5 The [language_complement] of an upwards closed [formal_language] is a [downwards_closed_language].
      6 
      7 Testing the [automaton_equivalence] of two [NFAs] recognizing downwards closed languages is [coNP_complete], cf [bachmeier2014finite]
      8 
      9 Up: [regular_language_family]
     10 
     11 See also: [higmans_lemma], [upwards_closure], [language_factor_minimal], [language_downwards_closed]
     12 
     13 Aliases: upward closed language, upward closed languages, upwards closed language, upwards closed languages