wiki_research

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

word_automaton_unambiguous (480B)

      1 # Unambiguous word automata
      2 
      3 [inclusion], [equivalence] are in P [ptime] (even NC [nc]?) whereas they are [pspace] PSPACE-c for
      4 [word_automaton_nondeterministic]
      5 
      6 More restricted definition: [word_automaton_self_verifying]
      7 
      8 Variant: [word_automaton_exclusive]
      9 
     10 [unambiguous_word_automaton_complementation]
     11 
     12 Up: [word_automaton], [unambiguity] 
     13 
     14 See also: [word_automaton_finitely_ambiguous], [word_automaton_polynomially_ambiguous]
     15 
     16 Aliases: UFA, UFAs, unambiguous word automaton