commit 8fc6e8ef3f34ab87864ff9f26776b5c7d6598239 parent be2f86b6f7533bef524cc729ae6bf75bdc626032 Author: Antoine Amarilli <a3nm@a3nm.net> Date: Wed, 21 Oct 2026 18:03:52 +0200 commit with codex Diffstat:
37 files changed, 138 insertions(+), 19 deletions(-)
diff --git a/3sum b/3sum @@ -12,6 +12,8 @@ used for hardness of pattern matching tasks, cf [amir2014hardness] can be done in time O(N log N) for N the maximal value using [fast_fourier_transform] +refutation claimed in [alman2026truly] + Up: [fine_grained_complexity_problems] See also: [negative_triangle], [ov_conjecture] diff --git a/algorithms_on_compressed_data b/algorithms_on_compressed_data @@ -5,7 +5,8 @@ name given in [lohrey2024enumeration] - [pattern_matching_compressed] - [enumeration_slp] - [lohrey2024enumeration] for [enumeration_mso] +- [compressed_string_indexing] Up: [compression], [algorithms] -See also: [compression_algorithm], [SLP] +See also: [compression_algorithm], [SLP], [indexing_repetitive_string_collections] diff --git a/automaton_query_complexity b/automaton_query_complexity @@ -4,5 +4,8 @@ The [query_complexity] of membership to the [formal_language] accepted by an [au - [aaronson2019quantum] studies it for [quantum_complexity] and in particular talks about the fact that it is either constant or linear depending on the language - [automaton_query_complexity_nondeterministic] +- [conditional_membership]: cf [amarilli2026conditional] -Up: [query_complexity] +Up: [query_complexity], [regular_language_membership] + +Aliases: query complexity regular language, regular language query complexity, query complexity regular language membership, regular_language membership query complexity diff --git a/cartesian_product b/cartesian_product @@ -5,6 +5,6 @@ The *cartesian product* of two [sets] S and T is the [set] of [ordered_pairs] Up: [mathematics] -See also: [join_query], [Decomposability] +See also: [join_query], [Decomposability], [cartesian_tree] Aliases: cartesian products diff --git a/cartesian_tree b/cartesian_tree @@ -0,0 +1,7 @@ +# Cartesian tree + +https://en.wikipedia.org/wiki/Cartesian_tree + +See also: [cartesian_product] + +Up: [stringology] diff --git a/compression_string b/compression_string @@ -4,6 +4,7 @@ - [lempel_ziv] - [burrows_wheeler_transform] - [substring_complexity] +- [compressed_string_indexing] Up: [compression], [string] diff --git a/context_free_language_membership b/context_free_language_membership @@ -8,3 +8,5 @@ Up: [membership_problem], [context_free_language] See also: [context_free_grammar_membership] + +Aliases: CFL membership diff --git a/counting_query_answers b/counting_query_answers @@ -10,4 +10,4 @@ Up: [counting_problem] Aliases: query answer counting, answer counting -See also: [homomorphism_counts_problem] +See also: [homomorphism_counts_problem], [minimum_match_counting] diff --git a/database_theory b/database_theory @@ -5,6 +5,7 @@ - [database_theory_techniques] - [database_theory_concepts] - [database_theory_complexity] +- [database_theory_neighboring_areas] - [query_language] - [graph_query_languages] diff --git a/database_theory_neighboring_areas b/database_theory_neighboring_areas @@ -0,0 +1,16 @@ +# Database theory neighboring areas + +- [parameterized_complexity] + - [database_theory_parameterized_complexity] +- [logic] +- [finite_model_theory] +- [algorithms] +- [data_structures] +- [database_research_practice] +- [machine_learning] +- [enumeration_algorithms] +- [knowledge_compilation] +- [formal_language_theory] +- [fine-grained_complexity] + +Up: [database_theory] diff --git a/database_theory_parameterized_complexity b/database_theory_parameterized_complexity @@ -0,0 +1,7 @@ +# Database theory parameterized complexity + +[grohe2002parameterized] + +Up: [database_theory_neighboring_areas], [parameterized_complexity], [database_theory] + +See also: [data_complexity], [Combined_complexity] diff --git a/datalog_query_evaluation b/datalog_query_evaluation @@ -8,7 +8,7 @@ - empty input [database] - one single [datalog_rule] - two-element universe -- for [datalog_linear]: +- for [linear_datalog]: - [pspace_complete] - already [pspace_hard] with the following, cf [gottlob2023complexity] - empty input [database] diff --git a/dominating_set b/dominating_set @@ -8,10 +8,12 @@ A subset of vertices of a graph such that every vertex of the graph is either in [karthik2019parameterized]: no [fixed_parameter_tractable] [approximation] algorithm for the problem - uses [abboud2017distributed] -Generalization: [generalized_dominating_set] +Generalizations: +- [generalized_dominating_set] +- [domination_number] Variant: [independent_dominating_set] -See also: [edge_dominating_set] +See also: [edge_dominating_set], [maximal_independent_set] Up: [graph_substructure] diff --git a/graph_database b/graph_database @@ -6,6 +6,7 @@ A [database_instance] on a [relational_signature] where each [database_relation] - [basic_graph_pattern]: a graph pattern with variables and constants - [regular_path_query] +- [word_equations], see [barcelo2017graph] Course notes: [figueira2023foundations] diff --git a/grid_minor b/grid_minor @@ -14,4 +14,4 @@ Up: [theorem] about [grid_graph] See also: [grid_minor_directed], [treewidth], [polynomial_grid_minor_theorem] -Aliases: grid minor extraction, grid extraction +Aliases: grid minor extraction, grid extraction, grid minors diff --git a/independent_set b/independent_set @@ -26,7 +26,7 @@ An *independent set* is a [subset] of [vertices] of an [undirected_graph] such t [fractional_independent_set] - like [fractional_edge_cover] vs [edge_cover] -See also: [matching], [vertex_cover], [empty_graph] +See also: [matching], [vertex_cover], [empty_graph], [independence_number] Up: [graph_substructure] diff --git a/lowest_common_ancestor_problem b/lowest_common_ancestor_problem @@ -5,4 +5,8 @@ Given two [nodes] in a [tree], find their [LCA] A [tree] can be [preprocessed] in [linear_time] to support such queries in [constant_time] - cf https://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm +[lowest_common_ancestor_problem_dynamic] + Up: [computational_problem], [lowest_common_ancestor] + +Aliases: LCA query, LCA queries diff --git a/lowest_common_ancestor_problem_dynamic b/lowest_common_ancestor_problem_dynamic @@ -0,0 +1,8 @@ +# Lowest common ancestor problem dynamic + +[cole1999dynamic]: +- worst-case contsant time for: + - [LCA_queries] + - [tree_updates]: insertion and deletion of leaves + +Up: [lowest_common_ancestor_problem], [dynamic_data] diff --git a/matching_patterns_with_variables_automata b/matching_patterns_with_variables_automata @@ -0,0 +1,11 @@ +# Pattern matching automata + +[matching_patterns_with_variables] on [automata]: given an [automaton] A and a [pattern_with_variables] p, does A accept a word that matches p + +The [decision_problem] is [PSPACE_complete] in [combined_complexity] + +studied in [anderson2009detecting] and [rampersad2010detecting] + +Up: [matching_patterns_with_variables], [automata] + +Aliases: DFA pattern acceptance, NFA pattern acceptance, automaton pattern acceptance, pattern acceptance diff --git a/maximal_independent_set b/maximal_independent_set @@ -2,8 +2,10 @@ - [maximal_independent_set_counting] +Every maximal independent set is also a [dominating_set] + Up: [independent_set] -See also: [maximum_independent_set] +See also: [maximum_independent_set], [independence_number] Aliases: maximal independent sets diff --git a/minimum_match_counting b/minimum_match_counting @@ -0,0 +1,9 @@ +# Minimum match counting + +The [counting_problem]: +- [input]: a [Boolean_query] Q and a [database_instance] D +- [output]: counting the [minimal_matches] of Q on D + +Up: [counting_query_answers] + +See also: [minimal_witness] diff --git a/pattern_matching b/pattern_matching @@ -22,6 +22,7 @@ - [approximate_pattern_matching] - [maximal_exact_match] - [internal_pattern_matching] +- [pattern_matching_state_complexity] ## Generalizations diff --git a/pattern_matching_ranges b/pattern_matching_ranges @@ -0,0 +1,11 @@ +# Pattern matching ranges + +- [makinen2006position] +- [hon2012position] + - "position restricted substring searching" + +Up: [range_query], [pattern_matching] + +See also: [direct_access] + +Aliases: position restricted substring searching, PRSS diff --git a/pattern_matching_state_complexity b/pattern_matching_state_complexity @@ -0,0 +1,7 @@ +# Pattern matching state complexity + +see [brozozwski2019state] + +Up: [pattern_matching], [state_complexity] + +Aliases: state complexity pattern matching diff --git a/pattern_with_variables_one_variable b/pattern_with_variables_one_variable @@ -2,4 +2,8 @@ [kosolobov2017detecting] (also with reversal) +Generalization: [regular_typed_pattern_languages_one_variable] + Up: [pattern_with_variables] + +Aliases: pattern with variable one variable, Patterns with only one variable, Pattern with only one variable diff --git a/prefix_free_language b/prefix_free_language @@ -2,8 +2,10 @@ A [formal_language] L is *prefix-free* if, whenever u and v are in L and u is a [prefix] of v, then u = v +Used for [pattern_matching], see [han2007prefix] + Up: [prefix] -See also: [suffix_free_language], [bifix_free_language] +See also: [suffix_free_language], [bifix_free_language], [deterministic_regular_expression] -Aliases: prefix free +Aliases: prefix free, prefix-free, prefix-free language, prefix code diff --git a/primitive_word b/primitive_word @@ -11,6 +11,6 @@ Special cases: Up: [word] -See also: [prime_number], [prime_number_decomposition], [primitive_word_conjecture], [composite_word] +See also: [prime_number], [prime_number_decomposition], [primitive_word_conjecture], [composite_word], [periodic_word], [word_period] Aliases: primitive words diff --git a/range_query b/range_query @@ -8,6 +8,7 @@ Maintain a collection of points and answer queries asking about all the points i - [gupta1995further]: range color counting/reporting in [rectangle] - [range_query_dynamic] - [range_distinctness_query] +- [pattern_matching_ranges] See also: [skyline], [2d_range_reporting], [range_reporting], [range_tree] diff --git a/regular_language_membership b/regular_language_membership @@ -7,4 +7,4 @@ Up: [membership_problem] for [regular_language] -See also: [language_distance_problem] +See also: [language_distance_problem], [CFL_membership] diff --git a/repetitive_string b/repetitive_string @@ -4,6 +4,6 @@ A [word] containing a nonempty [square_word] as a [factor] Up: [square_word] -See also: [square_free_word], [repetitive_string_language] +See also: [square_free_word], [repetitive_string_language], [indexing_repetitive_string_collections] Aliases: repetitive strings diff --git a/sequence b/sequence @@ -25,4 +25,8 @@ - [skolem_problem] +## [Computational_problems] + +- [sequence_alignment] + Up: [mathematics] diff --git a/sequence_alignment_regular_language b/sequence_alignment_regular_language @@ -0,0 +1,8 @@ +# Sequence alignment regular language + +[sequence_alignment] but constrained by a [regular_language] + +- [navarrete2020practical] +- [kucherov2011regular] + +Up: [sequence_alignment], [regular_language] diff --git a/smallest_witness b/smallest_witness @@ -1,7 +1,7 @@ # Minimal witness Find the smallest subset of a [relational_database] that satisfies a [query] -- formally, for query Q and database D, find smallest subset D' of D giving the same result +- formally, for query Q and database D, find smallest subset D' of D giving the same result, cf [minimal_match] - [approximation]: find a subset of tuples giving the same results which is within a [approximation_multiplicative] factor of the size of the optimal subset easy for [full_CQs], so hardness comes from [projection] diff --git a/sorting b/sorting @@ -7,6 +7,6 @@ Up: [algorithms] -See also: [permutation], [sorted_list] +See also: [permutation], [sorted_list], [sorted_order] Aliases: sort, sorts, sorted diff --git a/spanner_core b/spanner_core @@ -7,7 +7,7 @@ Other way to see it: [query] over the result of [spanners] Extension: [generalized_core_spanner] -See also: [refl_spanner] +See also: [refl_spanner], [core_spanner_dichotomies] Up: [spanner] diff --git a/subsequence_testing_gap_constraints b/subsequence_testing_gap_constraints @@ -7,6 +7,10 @@ - gaps are specified with length intervals and automata given as [DFAs] - with only length constraints, cf [iliopoulos2007algorithms] +- [amarilli2027tractable] + Up: [subsequence_testing], [gap_constraints] See also: [gapped_pattern_matching], [p_subsequence], [gapped_string_indexing], [subsequence_embedding] + +Aliases: constrained gaps diff --git a/synchronizing_sets b/synchronizing_sets @@ -2,6 +2,6 @@ construction in [ellert2026time] -See also: [synchronizing_word] +See also: [synchronizing_word], [String_attractor] Up: [stringology]