wiki_research

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

vector_addition_system (923B)

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