wiki_research

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

automaton_upwards_closed (953B)

      1 # Upwards closed automaton
      2 
      3 Deciding if the language of an [NFA] is [language_upwards_closed] is [PSPACE_complete] even on an alphabet of size 2, cf [karandikar2016deciding] Proposition 7.1. But it is [NL_complete] on [DFAs]
      4 
      5 Testing the [automaton_equivalence] of two [NFAs] recognizing upwards closed languages is [coNP_complete], cf [bachmeier2014finite]
      6 
      7 [automaton_inclusion_upwards_closed]
      8 
      9 Ditto for [automaton_inclusion], cf [karandikar2016state] Proposition 7.3
     10 
     11 All of this holds even if only the right-hand-side [NFA] is upwards-closed, cf also [inclusion_DFA_trick]
     12 
     13 [universality_automaton_upwards_closed]
     14 
     15 Up: [language_upwards_closed]
     16 
     17 Aliases: upwards closed automaton, Upwards closed automata, automaton subword closed, subword closed automaton, subword closed automata, supersequence closed automaton, supersequence closed automata, automata supersequence closed, automaton supersequence closed
     18 
     19 See also: [downwards_closed_automaton]