wiki_research

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

automata_evaluation (626B)

      1 # Automata evaluation
      2 
      3 Given an [automaton] A and a [word] w, determine if A accepts w
      4 
      5 - for [DFAs]: [DFA_acceptance]
      6   - can be done in O(|w|), simply by following [transitions]
      7 - for [NFAs]: [NFA_acceptance]
      8   - can be done in O(|w| |A|) by [state_set_simulation]
      9   - [conditional_lower_bound] in [backurs2016which]
     10     - reduction from [OV_conjecture]
     11 
     12 - [automata_evaluation_practice]
     13 
     14 See also: [regular_language_membership], [amarilli2025linear]
     15 
     16 Aliases: automaton membership, automata membership, automaton acceptance, automata acceptance, automaton evaluation
     17 
     18 Up: [automata_problems], [regular_language_membership]