commit 997e84b7b1ea79aeb9a8f5a40d9b1dd2782d2a96
parent 5fae146d5b850d55afea187ad1014f47c21b7b0c
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sat, 11 Oct 2025 09:06:56 +0200
commit with codex
Diffstat:
2 files changed, 8 insertions(+), 1 deletion(-)
diff --git a/pushdown_automaton b/pushdown_automaton
@@ -10,7 +10,7 @@ Restricted cases:
[Computational_problems]:
- [universality_automata_pushdown]
-Up: [stack_automata]
+Generalization: [stack_automaton]
See also: [visibly_pushdown_automaton], [pushdown_automaton_two_way]
diff --git a/vector_addition_system b/vector_addition_system
@@ -1,5 +1,7 @@
# Vector addition system (VAS)
+Also called "vector addition system with states" (VASS)
+
- Like a [word_automaton] but with a configuration featuring a vector
- Transitions add a vector to the current vector
- They can only be taken if every coordinate remains positive
@@ -16,6 +18,11 @@ Complexity of the [reachability] problem: [ackermann_function]
two-dimensional VAS with one test on counters, like [counter_automata]: [leroux2020reachability]
+Restrictions:
+
+- [1_VASS], with only one counter
+ - see also [one_conter_automata]
+
Up: [automata]
See also: [counter_automata]
