commit 0236ba408f78cf452a4fd00b445e6e3198cf789c
parent 064a10f7b1d2a892195a5069dcbcdea95779437c
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 12 Feb 2025 21:09:34 +0100
commit with codex
Diffstat:
12 files changed, 48 insertions(+), 4 deletions(-)
diff --git a/backurs2016which b/backurs2016which
@@ -2,4 +2,6 @@
uses [strong_exponential_time_hypothesis] and [orthogonal_vectors]
+[follow_up]: [bringmann2016dichotomy]
+
Up: [academic_paper] on [regular_expression_matching]
diff --git a/complementation b/complementation
@@ -2,6 +2,7 @@
- [ddnnf_complementation]
- [graph_complementation]
+- [language_complementation]
Up: [logic], [boolean_operator]
diff --git a/downwards_closure b/downwards_closure
@@ -0,0 +1,13 @@
+# Downwards closure
+
+For L a [formal_language], the *downwards closure* of L is the set of [words] w which are [subsequences] of a word of L
+
+For any [formal_language] L, the downwards closure is a [regular_language]: this uses [Higman's_lemma]
+
+The downwards closure is a [downwards_closed_language]: any [subsequence] of a [word] of the downwards closure is in the downwards closure
+
+See also: [language_downwards_closed], [upwards_closure]
+
+Up: [formal_language_operator], [closure_operation] on [subsequences]
+
+Aliases: downward closure
diff --git a/greedy_algorithm b/greedy_algorithm
@@ -5,3 +5,5 @@ Algorithm where you can build an optimal solution step by step by making choices
See also: [matroid]
Up: [algorithm_type]
+
+Aliases: greedily
diff --git a/language_upwards_closed b/language_upwards_closed
@@ -0,0 +1,11 @@
+# Language upwards closed
+
+A [formal_language] is *upwards closed* if any [subword] of the [formal_language] is in the [formal_language]
+
+The [language_complement] of an upwards closed [formal_language] is a [downwards_closed_language].
+
+Up: [regular_language_family]
+
+See also: [higmans_lemma], [upwards_closure], [language_factor_minimal], [language_downwards_closed]
+
+Aliases: upward closed language, upward closed languages, upwards closed language, upwards closed languages
diff --git a/regular_expression_deterministic b/regular_expression_deterministic
@@ -6,6 +6,7 @@
[groz2012deterministic] and [groz2017efficient]
- can check in [linear_time] if [regular_expression] is deterministic
- can perform [regular_expression_matching] in O(n log log m + m)
+ - [regular_expression_deterministic_matching]
according to [freydenberger2019deterministic], also an algorithm in O(|Sigma| m + n)
diff --git a/rpq_query_evaluation b/rpq_query_evaluation
@@ -4,6 +4,7 @@ survey: [barcelo2013querying]
- naive algorithm: [product_graph]
- more efficient algorithm in [abokhamis2024output]
+ - for [CRPQs]: [cucumides2023size]
- [rpq_fine_grained]
- [rpq_trichotomies]
@@ -13,3 +14,5 @@ survey: [barcelo2013querying]
- [rpq_output_sensitive]
Up: [regular_path_query], [query_evaluation]
+
+Aliases: RPQ evaluation
diff --git a/subsequence b/subsequence
@@ -15,8 +15,9 @@
- [longest_common_supersequence] [timkovsky1989complexity]
- [longest_increasing_subsequence]
- [p_subsequence]
+- [subsequence_automaton]
-See also: [subword], [sequence], [subword]
+See also: [subword], [sequence], [subword], [supersequence]
Up: [formal_language_theory], [stringology]
diff --git a/subsequence_testing b/subsequence_testing
@@ -7,4 +7,4 @@ testing if an (entire) word u is a [subsequence] of another word v
Up: [computational_problem], [subsequence]
-See also: [pattern_matching]
+See also: [pattern_matching], [subsequence_embedding]
diff --git a/subsequence_testing_gap_constraints b/subsequence_testing_gap_constraints
@@ -4,9 +4,9 @@
- [day2022subsequences]
- gap equalities make problem [NP_complete] (Section 5)
- - gaps are specified with length intervals and automata given as [DFA]s
+ - gaps are specified with length intervals and automata given as [DFAs]
- with only length constraints, cf [iliopoulos2007algorithms]
Up: [subsequence_testing], [gap_constraints]
-See also: [gapped_pattern_matching], [p_subsequence], [gapped_string_indexing]
+See also: [gapped_pattern_matching], [p_subsequence], [gapped_string_indexing], [subsequence_embedding]
diff --git a/supersequence b/supersequence
@@ -0,0 +1,9 @@
+# Supersequence
+
+A [word] u is a *supersequence* of a [word] v if v is a [subsequence] of u
+
+See also: [subsequence]
+
+Up: [formal_language_theory], [stringology]
+
+Aliases: supersequences
diff --git a/union b/union
@@ -2,5 +2,6 @@
- [union_trick]
- [disjoint_union]
+- [language_union]
Up: [set_theory], [boolean_operator]
