wiki_research

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

automaton_upwards_closed (908B)

      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, supersequence closed automaton, supersequence closed automata, automata supersequence closed, automaton supersequence closed
     18 
     19 See also: [downwards_closed_automaton], [automaton_subsequence_closed]