wiki_research

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

universality_automata_nondeterministic (324B)

      1 # Universality automata nondeterministic
      2 
      3 [conp_complete] even on [unary_alphabet]:
      4 - https://cs.stackexchange.com/a/97751
      5 
      6 The shortest rejected word of an automaton with O(n) states may be Omega(n 2^n): cf [ellul2005regular], Theorem 32
      7 
      8 Up: [universality_automata], [automata_nondeterministic]
      9 
     10 Aliases: NFA universality