wiki_research

commit 00c74fa1a87db73fcbd9ff7b1b3788e46df1c14b
parent 8fc6e8ef3f34ab87864ff9f26776b5c7d6598239
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Wed, 21 Oct 2026 18:03:53 +0200

Merge remote-tracking branch 'origin/master'

Diffstat:
shuffle_membership
 | 
7
+++----
shuffle_membership_language
 | 
9
+++++++++
shuffle_product_problem
 | 
9
+++++++--

3 files changed, 19 insertions(+), 6 deletions(-)
diff --git a/shuffle_membership b/shuffle_membership
@@ -1,9 +1,8 @@
 # Shuffle membership
 
-The [language_membership_problem] to a [formal_language] which is the [shuffle] of two [formal_languages]:
+- [shuffle_membership_language]: for the [shuffle] of two [formal_languages]
+- [shuffle_membership_word]: for the [shuffle] of [words]
 
-- e.g., [berglund2012membership] shows [NP_hardness] of that problem for the [shuffle] of two [deterministic_linear_CFLs]
-
-Up: [shuffle]
+Up: [shuffle], [membership_problem]
 
 See also: [Constrained_topological_sort]
diff --git a/shuffle_membership_language b/shuffle_membership_language
@@ -0,0 +1,9 @@
+# Shuffle membership language
+
+The [language_membership_problem] to a [formal_language] which is the [shuffle] of two [formal_languages]:
+
+- e.g., [berglund2012membership] shows [NP_hardness] of that problem for the [shuffle] of two [deterministic_linear_CFLs]
+
+Up: [shuffle_membership], [formal_language]
+
+See also: [shuffle_membership_word]
diff --git a/shuffle_product_problem b/shuffle_product_problem
@@ -4,8 +4,13 @@ The [computational_problem], given [words] s1, ..., sk, and t, of [deciding] whe
 
 can be done with [dynamic_programming], which gives a [polynomial_time] [algorithm] if k is a constant
 
+is [NP_hard] for unbounded k
+- see Problem 3 in [giraudo2016unshuffling]
+
 [complete] for [XNLP], cf [bodlaender2026parameterized]
 
-Up: [computational_problem], [shuffle]
+Up: [shuffle_membership]
+
+See also: [shuffle_product], [shuffle_membership_language]
 
-See also: [shuffle_product]
+Aliases: shuffle membership word, shuffle membership words