commit 7d8bcbb3b969055ac63270753e82aecbd0421664
parent 06a682a00437558ae9e39e19cbf037d436c20b11
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 29 Sep 2026 19:20:52 +0200
commit with codex
Diffstat:
17 files changed, 61 insertions(+), 7 deletions(-)
diff --git a/alphabet b/alphabet
@@ -2,6 +2,9 @@
A finite [set] of [letters]
-Special case: [alphabet_unary]
+Special cases:
+
+- [unary_alphabet]
+- [binary_alphabet]
Up: [formal_language]
diff --git a/alphabet_unary b/alphabet_unary
@@ -1,6 +1,6 @@
-# Alphabet unary
+# Unary alphabet
-[Alphabet] which is a [singleton], i.e., contains one single [letter]
+An [alphabet] which is a [singleton], i.e., contains one single [letter]
- [language_unary]
- [automata_unary]
@@ -9,3 +9,5 @@
Up: [alphabet]
Aliases: unary alphabet, unary alphabets
+
+See also: [binary_alphabet]
diff --git a/block_independent_disjoint b/block_independent_disjoint
@@ -0,0 +1,7 @@
+# Block independent disjoint
+
+studied in [kanelloupoulos2026complexity]
+
+Up: [probabilistic_database_model]
+
+Aliases: BID
diff --git a/bruner2014computational b/bruner2014computational
@@ -2,4 +2,6 @@
subsumes [bruner2013w1]
+defines [segregated_permutation_pattern_matching], which is [W1_hard]
+
Up: [academic_paper] on [permutation_pattern_matching]
diff --git a/compressed_subsequence_testing b/compressed_subsequence_testing
@@ -0,0 +1,7 @@
+# Compressed subsequence testing
+
+The [computational_problem], given two [compressed_words] u and v, of [deciding] if u is a [subsequence] of v
+
+If u and v are given as [SLPs], it is [PSPACE_complete], even on a [binary_alphabet], cf [lohrey2026compressed]
+
+Up: [subsequence_testing], [compressed_word]
diff --git a/compression_string b/compression_string
@@ -7,4 +7,4 @@
Up: [compression], [string]
-Aliases: compressed string, compressed strings
+Aliases: compressed string, compressed strings, compressed word, compressed words
diff --git a/disjoint_paths_undirected b/disjoint_paths_undirected
@@ -4,7 +4,7 @@ Given an [undirected_graph] G and vertices s_1, t_1, ..., s_k, t_k, decide wheth
It is [NP_complete] if k is not fixed ([karp1975computational], cited in [liu2025disjoint])
-- For any constant k, by [Robertson_Seymour] it is [PTIME], in O(n^3), and even in [almost_linear_time] by [korhonen2024minor]
+- For any constant k, by [Robertson_Seymour] [robertson1995graph13], it is [PTIME] (in O(n^3)), and even in [almost_linear_time] by [korhonen2024minor]
- It is [FPT] parameterized by k
- cf also [lokshtanov2021exponential], on [planar_graphs], for the dependency on k
diff --git a/formal_language_complexity_measure b/formal_language_complexity_measure
@@ -4,5 +4,6 @@
- [language_density]
- [star_height]
- [generalized_star_height]
+- [formal_language_width]
Up: [formal_language]
diff --git a/formal_language_width b/formal_language_width
@@ -0,0 +1,7 @@
+# Formal language width
+
+The minimum [partial_order_width] of an [automaton] accepting the langugae
+
+cf [dagostino2026non]
+
+Up: [formal_language_complexity_measure]
diff --git a/grid_minor b/grid_minor
@@ -6,6 +6,7 @@ relevant [academic_papers]:
- [lanzinger2022complexity]
- [chekuri2016polynomial]
- [chuzhoy2021towards] for tighter bounds on grid minor extraction
+- https://laxarchive.org/lax-17/ bound with exponent 8 on [laxarchive]
used for [hardness] results, e.g., [grohe2007complexity]
diff --git a/pattern_matching b/pattern_matching
@@ -3,7 +3,7 @@
## [computational_complexity]
- [pattern_matching_algorithm]
-- [lower_bounds] on [combined_complexity]:
+- [lower_bounds] on [combined_complexity] for generalizations:
- [backurs2016which], cf [regular_expression_matching]
## [dynamic_data]
@@ -34,6 +34,7 @@
- [gapped_pattern_matching]: find two patterns separated by a distance within a specified range
- [text_index], when the text can be preprocessed
- [dictionary_matching]
+- [tree_pattern_matching]
## Implementations
diff --git a/permutation_pattern_matching b/permutation_pattern_matching
@@ -12,6 +12,7 @@ Generalizations:
- cf [bruner2014computational]
- with [parity_constraints]
- cf [ardevolmartinez2024parity]
+- [segregated_permutation_pattern_matching]
See also: [permutation], [vincular]
diff --git a/poset_width b/poset_width
@@ -7,3 +7,5 @@ Can be computed in [PTIME] via [dilworths_theorem] using a [flow_algorithm]
Up: [partial_order]
See also: [dilworths_theorem], [chain_partitioning], [partial_order_height], [poset_dimension]
+
+Aliases: partial order width
diff --git a/segregated_permutation_pattern_matching b/segregated_permutation_pattern_matching
@@ -0,0 +1,9 @@
+# Segregated permutation pattern matching
+
+defined in [bruner2014computational]
+
+[W1_complete]
+
+Up: [permutation_pattern_matching]
+
+Aliases: SPPM
diff --git a/separating_automaton b/separating_automaton
@@ -2,6 +2,10 @@
cf https://en.wikipedia.org/wiki/Separating_words_problem
-cf [chase2020separating]
+Relevant [academic_papers]:
+- [chase2020separating]
+- [bathie2026separating]
Up: [automata]
+
+Aliases: separating words
diff --git a/subsequence_testing b/subsequence_testing
@@ -5,6 +5,8 @@ testing if an (entire) word u is a [subsequence] of another word v
- generalization: [subsequence_testing_gap_constraints]
+- on [compressed_words]: [compressed_subsequence_testing]
+
Up: [computational_problem], [subsequence]
See also: [pattern_matching], [subsequence_embedding]
diff --git a/tree_pattern_matching b/tree_pattern_matching
@@ -0,0 +1,5 @@
+# Tree pattern matching
+
+studied in [kosaraju1998efficient]
+
+Up: [pattern_matching] on [trees]
