wiki_research

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

automaton_inclusion_downwards_closed (396B)

      1 # Automaton inclusion downwards closed
      2 
      3 Testing [automaton_inclusion] of two [NFAs] recognizing downwards closed languages is [coNP_complete], cf [karandikar2016state] Proposition 7.3
      4 
      5 All of this holds even if only the right-hand-side [NFA] is upwards-closed, cf also [inclusion_DFA_trick]
      6 
      7 Up: [automaton_inclusion], [automaton_downwards_closed]
      8 
      9 See also: [automaton_inclusion_upwards_closed]