wiki_research

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

vector_addition_system (1141B)

      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 [VASS_reachability] problem: [ackermann_function]
     17 - https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/
     18 - known to be [ackermann_complete]
     19 - the reachable sets are [almost_semi_linear]
     20 - complexity apparently still open when [dimension] is constant
     21 
     22 two-dimensional VAS with one test on counters, like [counter_automata]: [leroux2020reachability]
     23 
     24 They correspond to [Minsky_machines] but without zero tests
     25 
     26 Restrictions:
     27 
     28 - [1_VASS], with only one counter
     29   - see also [one_conter_automata]
     30 
     31 Up: [automata]
     32 
     33 See also: [counter_automata]
     34 
     35 Aliases: vector addition systems, VAS, VASes, VASS, VASSes