wiki_research

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

universality_automata_nondeterministic (348B)

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