wiki_research

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

automaton_inclusion (544B)

      1 # Automaton inclusion
      2 
      3 - [NFA_inclusion]: [PSPACE_complete]
      4 - [UFA_inclusion]: [PTIME] by reduction to [UFA_universality]
      5   - by reduction to [NXA_universality]:
      6     - cf https://cstheory.stackexchange.com/a/25478
      7 - [k_unambiguous_inclusion]
      8 - [DFA_inclusion]: [PTIME] via [product_construction]
      9 
     10 [inclusion_DFA_trick]
     11 
     12 [regular_language_inclusion_dichotomy]
     13 
     14 Special case: [automaton_universality]
     15 
     16 Up: [automata_problems], [language_inclusion]
     17 
     18 See also: [automaton_equivalence], [automaton_universality]
     19 
     20 Aliases: regular language inclusion