wiki_research

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

vector_addition_system (747B)

      1 # Vector addition system (VAS)
      2 
      3 - Like a [word_automaton] but with a configuration featuring a vector
      4   - Transitions add a vector to the current vector
      5   - They can only be taken if every coordinate remains positive
      6 
      7 [ginzburg1980vector]: determine when a VAS defines a [regular_language]
      8 
      9 Generalizations:
     10 - [vector_addition_tree_automata]
     11 - [vector_addition_system_pushdown]
     12 
     13 Complexity of the [reachability] problem: [ackermann_function]
     14 - https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/
     15 - apparently still open when [dimension] is constant
     16 
     17 two-dimensional VAS with one test on counters, like [counter_automata]: [leroux2020reachability]
     18 
     19 Up: [automata]
     20 
     21 See also: [counter_automata]