wiki_research

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

counter_automata_one (385B)

      1 # One-counter automata (OCA)
      2 
      3 Related concept: [one_counter_nets]
      4 
      5 Generalization: [counter_automata_trees]
      6 
      7 - [counter_automata_one_deterministic]
      8 
      9 [conversion] of OCA to [DFA] requires doubly exponential number of [states]
     10   - e.g., "the n-th character from the end is an a", with n coded in binary
     11 
     12 Up: [counter_automata]
     13 
     14 See also: [counter_automata_two], [vector_addition_system]