wiki_research

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

universality_automaton_downwards_closed (449B)

      1 # Automaton universality for downwards closed automata
      2 
      3 The [automaton_universality_problem] for [downwards_closed_automata] is [NL_complete], you simply have to check if there is an [SCC] containing all letters, cf [karandikar2016state] Proposition 7.4
      4 
      5 Up: [automaton_universality_problem], [automaton_downwards_closed]
      6 
      7 See also: [automaton_universality_for_upwards_closed_automata]
      8 
      9 Aliases: automaton universality for downwards closed automata