commit f8e5625ffd7c921eb56d48a9f01aced865e63d16
parent 7974de3bf9056966bc5b2ac6739be37ba81dd10c
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 31 Dec 2024 00:34:43 +0100
commit with codex
Diffstat:
2 files changed, 9 insertions(+), 0 deletions(-)
diff --git a/compressed_subword_problem b/compressed_subword_problem
@@ -0,0 +1,7 @@
+# Compressed subword problem
+
+Given two [straight_line_programs], decide if the first generates a [subword] of the second.
+
+[lohrey2012algorithmics]: this is [pp_hard] and in [pspace]
+
+Up: [ganardi2024directed]
diff --git a/straight_line_program b/straight_line_program
@@ -8,3 +8,5 @@ essentially a [context_free_grammar] that generates a single [string]: [acyclici
Up: [string_compression]
See also: [forest_straight_line_program]
+
+Aliases: SLP, SLPs, straight line programs
