wiki_research

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

automaton_inclusion_upwards_closed (392B)

      1 # Automaton inclusion upwards closed
      2 
      3 Testing [automaton_inclusion] on two [NFAs] recognizing upwards 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_upwards_closed]
      8 
      9 See also: [Automaton_inclusion_downwards_closed]