wiki_research

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

automaton_downwards_closed (960B)

      1 # Downwards closed automaton
      2 
      3 Deciding if the language of an [NFA] is [language_downwards_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 downwards closed languages is [coNP_complete], cf [bachmeier2014finite]
      6 
      7 Ditto for [automaton_inclusion], cf [karandikar2016state] Proposition 7.3
      8 
      9 [automaton_inclusion_downwards_closed]
     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_downwards_closed]
     14 
     15 See also: [automaton_upwards_closed]
     16 
     17 Up: [language_downwards_closed]
     18 
     19 Aliases: downwards closed automaton, downwards closed automata, subword closed automaton, subword closed automata, automaton subword closed, subsequence closed automaton, subsequence closed automaton, automaton subsequence closed, automata subsequence closed