wiki_research

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

language_downwards_closed (870B)

      1 # Language downwards closed
      2 
      3 A [formal_language] is *downwards closed* if any [subword] of the [formal_language] is in the [formal_language]
      4 
      5 [ideal_decomposition]: every downward closed language is a finite [union] of [language_ideal] i.e. terms of the form
      6 
      7   A_1^* {a_1, epsilon} ... A_k^*
      8   where the A_i are subalphabets
      9 
     10 [language_downwards_closed_details]
     11 
     12 The [language_complement] of a downwards closed [formal_language] is a [upwards_closed_language].
     13 
     14 Testing the [automaton_equivalence] of two [NFAs] recognizing downwards closed languages is [coNP_complete], cf [bachmeier2014finite]
     15 
     16 Up: [regular_language_family]
     17 
     18 See also: [higmans_lemma], [downwards_closure], [language_factor_minimal], [language_upwards_closed], [ganardi2024directed]
     19 
     20 Aliases: downward closed language, downward closed languages, downwards closed language, downwards closed languages