commit 98882fc207c2f2f6d1f1010759213f9bc85b9d12
parent 04e334bd126411e1c37b79c71a43ddd7e54531a7
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 18 Mar 2026 16:22:35 +0100
commit with codex
Diffstat:
5 files changed, 26 insertions(+), 3 deletions(-)
diff --git a/completely_reachable_automata b/completely_reachable_automata
@@ -0,0 +1,9 @@
+# Completely reachable automata
+
+An [automaton] where every nonempty subset of states can be achieved by applying some word on the set of all states
+
+See [ferens2026recognizing]
+
+See also: [cerny_conjecture]
+
+Up: [automata]
diff --git a/first_order_interpretation b/first_order_interpretation
@@ -15,4 +15,4 @@ Up: [logic_interpretation], [FO]
Aliases: FO interpretation, FO reduction
-See also: [FO_projection]
+See also: [FO_projection], [MSO_interpretation]
diff --git a/reachability b/reachability
@@ -4,6 +4,7 @@
- [st_reachability_undirected]
- [reachability_single_source]
- [reachability_all_pairs]
+- [VASS_reachability]
Up: [computational_problem], [graph_theory]
diff --git a/regular_language_polyslender b/regular_language_polyslender
@@ -0,0 +1,7 @@
+# Regular language polyslender
+
+A [regular_language] which is [language_polyslender]
+
+See [szilard1992characterizing] and [mathematical_foundations_of_automata_theory] Chapitre XII Section 4.2
+
+Up: [language_polyslender]
diff --git a/vector_addition_system b/vector_addition_system
@@ -13,12 +13,16 @@ Generalizations:
- [vector_addition_system_pushdown]
- [vector_addition_system_nested]
-Complexity of the [reachability] problem: [ackermann_function]
+Complexity of the [VASS_reachability] problem: [ackermann_function]
- https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/
-- apparently still open when [dimension] is constant
+- known to be [ackermann_complete]
+- the reachable sets are [almost_semi_linear]
+- complexity apparently still open when [dimension] is constant
two-dimensional VAS with one test on counters, like [counter_automata]: [leroux2020reachability]
+They correspond to [Minsky_machines] but without zero tests
+
Restrictions:
- [1_VASS], with only one counter
@@ -27,3 +31,5 @@ Restrictions:
Up: [automata]
See also: [counter_automata]
+
+Aliases: vector addition systems, VAS, VASes, VASS, VASSes
