wiki_research

commit ab1c0b7a57be1e3f903f74559dac9b6d79646550
parent 879df527394727dc285bdb55e90f329b22acd597
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue,  3 Mar 2026 10:14:56 +0100

Merge remote-tracking branch 'origin/master'

Diffstat:
backreferences
 | 
2
+-
cerny_conjecture
 | 
2
++
cut_ranked_enumeration
 | 
5
+++--
cycle_induced
 | 
2
++
detour_problem
 | 
9
+++++++++
lz77
 | 
7
+++++++
matrix_multiplication
 | 
2
++
matrix_multiplication_twinwidth
 | 
5
+++++
redos_backreferences
 | 
5
+++++
regular_expression_denial_of_service
 | 
3
+++
shortest_path
 | 
2
+-
synchronizing_word
 | 
2
+-
twin_width
 | 
2
++
vector_addition_system_pushdown
 | 
4
+++-

14 files changed, 46 insertions(+), 6 deletions(-)
diff --git a/backreferences b/backreferences
@@ -6,4 +6,4 @@ Up: [regular_expression]
 
 See also: [refl_spanner], [spanner], [capture_variable]
 
-Aliases: back reference, back references, back-reference, back-references
+Aliases: back reference, back references, back-reference, back-references, regular expression backreference, regular expression backreferences
diff --git a/cerny_conjecture b/cerny_conjecture
@@ -5,3 +5,5 @@ https://en.wikipedia.org/wiki/Synchronizing_word
 It is known that an [automata] with a [synchronizing_word] may have no smaller synchronizing word than length (n-1)^2: is there a matching upper bound?
 
 Up: [synchronizing_word]
+
+See also: [completely_reachable_automata]
diff --git a/cut_ranked_enumeration b/cut_ranked_enumeration
@@ -3,8 +3,9 @@
 [Enumeration] of [cuts] with [polynomial_delay]
 
 - [picard1979structure]
-- [vazirani1992suboptimal]
+- [vazirani1992suboptimal] to find nonoptimal [cuts]
+  - see also https://cstheory.stackexchange.com/questions/48803/how-to-find-the-second-smallest-cut-in-a-graph
 
-Up: [ranked_enumeration] of [cut]
+Up: [ranked_enumeration] of [cuts]
 
 See also: [beideman2022deterministic]
diff --git a/cycle_induced b/cycle_induced
@@ -5,6 +5,8 @@
 - [triangle]
 - [hole]: induced cycle of length at least 4
 
+Distinct induced cycle lengths: [chudnovsky2026induced]
+
 Up: [cycle]
 
 Aliases: induced cycle
diff --git a/detour_problem b/detour_problem
@@ -0,0 +1,9 @@
+# Detour problem
+
+https://a3nm.net/work/research/questions/#detour-problem
+
+Given a [directed_graph] and s and t, decide if there is a [simple_path] from s to t which is not a [shortest_path]
+
+Related work on [induced_paths] in [undirected_graphs]: [berger2021finding]
+
+Up: [shortest_path]
diff --git a/lz77 b/lz77
@@ -0,0 +1,7 @@
+# LZ77
+
+[sensitivity], cf [bathie2026analyzing]
+
+Up: [compression_algorithm]
+
+See also: [one_bit_catastrophe]
diff --git a/matrix_multiplication b/matrix_multiplication
@@ -10,6 +10,8 @@ In specific [semirings]:
   - open question of what is the best exponent
   - [omm_conjecture]
 
+- [matrix_multiplication_twinwidth]
+
 Up: [multiplication] of [matrix]
 
 See also: [algorithm], [matrix_product]
diff --git a/matrix_multiplication_twinwidth b/matrix_multiplication_twinwidth
@@ -0,0 +1,5 @@
+# Matrix multiplication twinwidth
+
+Can use [twinwidth] to give good [upper_bounds] on [matrix_multiplication], cf [kozma2026fast]
+
+Up: [matrix_multiplication], [twinwidth]
diff --git a/redos_backreferences b/redos_backreferences
@@ -0,0 +1,5 @@
+# Redos backreferences
+
+cf [liu2026regular]
+
+Up: [regular_expression_denial_of_service], [backreferences]
diff --git a/regular_expression_denial_of_service b/regular_expression_denial_of_service
@@ -6,6 +6,9 @@ Mentioned in [moseley2023derivative]
 
 [parolini2023sound]: [static_analysis] to identify denial of service
 
+- for [regular_expression_counting]: [redos_counting]
+- for [regular_expression_backreferences]: [redos_backreferences]
+
 Up: [regular_expression], [denial_of_service]
 
 Aliases: [redos]
diff --git a/shortest_path b/shortest_path
@@ -22,6 +22,6 @@ Variants:
 
 Up: [graph_problem]
 
-See also: [minmax_path], [reachability], [transitive_closure]
+See also: [minmax_path], [reachability], [transitive_closure], [detour_problem]
 
 Aliases: shortest paths
diff --git a/synchronizing_word b/synchronizing_word
@@ -4,4 +4,4 @@
 
 Up: [automata]
 
-See also: [mortal_word], [meeting_time], [synchronizing_sets], [synchronizing_word_problem]
+See also: [mortal_word], [meeting_time], [synchronizing_sets], [synchronizing_word_problem], [completely_reachable_automata]
diff --git a/twin_width b/twin_width
@@ -26,3 +26,5 @@ guarantees that [first_order_model_checking_parameterized_complexity] is [fixed_
 Up: [width_measure]
 
 See also: [nowhere_dense], [merge_width]
+
+Aliases: twinwidth
diff --git a/vector_addition_system_pushdown b/vector_addition_system_pushdown
@@ -2,7 +2,9 @@
 
 [vector_addition_system] with [pushdown_automaton] store
 
-Unclear if [reachability] is [decidable], cf [ganardi2022reachability]
+Unclear if [reachability] is [decidable]
+- cf [ganardi2022reachability]
+- claimed decidable in [guttenberg2026pvass]
 
 Also with counters and with resets [schmitz2019coverability] (but for [coverability])