wiki_research

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

automata_evaluation (373B)

      1 # Automata evaluation
      2 
      3 Given an [automaton] A and a [word] w, determine if A accepts w
      4 
      5 - for [DFAs]: can be done in O(|w|), simply by following [transitions]
      6 - for [NFAs]: can be done in O(|w| |A|) by [state_set_simulation]
      7   - [conditional_lower_bound] in [backurs2016which]
      8     - reduction from [OV_conjecture]
      9 
     10 - [automata_evaluation_practice]
     11 
     12 Up: [automata_problems]