commit 642798d43fdeee53aa938da66dab3a86928ece7e parent afba233961e14eccde707fa761f6628a56eb1cf7 Author: Antoine Amarilli <a3nm@a3nm.net> Date: Sun, 22 Jun 2025 14:23:35 +0200 cleanup Diffstat:
50 files changed, 71 insertions(+), 86 deletions(-)
diff --git a/access_pattern b/access_pattern @@ -3,7 +3,7 @@ [academic_papers]: - [kara2022conjunctive] [incremental_maintenance] -- [zhao2023space]: [complexity_space]/[complexity_time] tradeoff +- [zhao2023space]: [complexity_space] vs [complexity_time] tradeoff Up: [database_theory] diff --git a/acyclic_free_connex b/acyclic_free_connex @@ -1,6 +1,6 @@ # Acyclic free-connex -Subclass of [conjunctive_query_acyclic] which remains acyclic when adding an atom covering the [free_variable]s +Subclass of [conjunctive_query_acyclic] which remains acyclic when adding an atom covering the [free_variables] Some people don't say "acyclic" and take "free-connex" to mean "acyclic free-connex" diff --git a/algebraic_automata_theory b/algebraic_automata_theory @@ -2,7 +2,7 @@ - [variety] closed under [inverse_morphism], left/right [quotient], [sublanguage], [boolean_set_operation] including [complementation] - - [variety_li] li-variety: closure only under inverses of length-increasing [length_increasing_morphism] pin2016dot + - [variety_li] li-variety: closure only under inverses of length-increasing [length_increasing_morphism] [pin2016dot] - connection to notion of +-variety - lm-variety? - Eilenberg's variety theorem [eilenbergs_theorem]: varieties of [monoid] diff --git a/approximation_multiplicative b/approximation_multiplicative @@ -2,7 +2,7 @@ Possible for [sharp_satisfiability] for [disjunctive_normal_form], and many other problems -Another example is arenas2021nfa +Another example is [arenas2021nfa] See also: [approximation_additive], [fpras] diff --git a/automata_reversible b/automata_reversible @@ -8,7 +8,8 @@ Extends [automata_bideterministic] by lifting the requirement of having exactly Class of [formal_language] accepted by a reversible automaton - is closed under [union] -- membership given an [automata] can be tested in [ptime] pin1992reversible +- membership given an [automata] can be tested in [ptime] + - [pin1992reversible] See also: [turing_machine_symmetric], [automata_symmetric], [transducer_reversible] diff --git a/automata_weighted b/automata_weighted @@ -9,7 +9,7 @@ associates each [word] to an [integer], or to a value in a [semiring] - weight for every [transition] given a [word]: -- [sum] over possible [run]s +- [sum] over possible [runs] - [product] over [transitions] and [final_states] used Can be seen as multiplying [matrices] (one [matrix] for each letter), with a [vector] of [initial_weights] and [final_weights] diff --git a/circuit b/circuit @@ -22,10 +22,6 @@ - [enumeration_circuit] - [satisfiability] -## Notions - -- [circuit_trace] - ## Measure [circuit_parameter] - [depth] @@ -42,6 +38,7 @@ - [gate] - [wire] +- [circuit_trace] ## Research diff --git a/circuit_size b/circuit_size @@ -1,6 +1,6 @@ # Circuit size -can be number of [gate]s, or number of [wire]s +can be number of [gates], or number of [wires] - [circuit_lower_bound] diff --git a/combinatorics b/combinatorics @@ -23,7 +23,7 @@ - [universal_tree] https://games-automata-play.github.io/blog/universal_trees/ - [sparse_rulers] - [golomb_ruler] / [sidon_set] -- sequences without [arithmetic_progression]s +- sequences without [arithmetic_progressions] - [salem_spencer_set] - [angel_problem] - [german_tank_problem] diff --git a/conjunctive_query_signed b/conjunctive_query_signed @@ -1,9 +1,9 @@ # CQ with negated atoms -a [conjunctive_query] with [negation] on some [atom]s +a [conjunctive_query] with [negation] on some [atoms] - [capelli2023direct] - - also zhao2023conjunctive + - also [zhao2023conjunctive] - [fink2016dichotomies] - [enumeration_cqs]: see [segoufin2015constant] which cites [brault2014pertinence] diff --git a/counting_cqs b/counting_cqs @@ -9,7 +9,7 @@ Results: - Exact counting is [sharpp_complete] in [query_complexity] - For [acyclic_CQs]: [ptime] with counting variant of [Yannakakis's_algorithm] - For bounded [generalized_hypertree_width]: - - [arenas2021when]: approximate counting [fpras] for bounded [generalized_hypertree_width]generalized_hypertree_width + - [arenas2021when]: approximate counting [fpras] for bounded [generalized_hypertree_width] - extended by [vanbremen2023probabilistic] - [self-joins] can be a problem diff --git a/counting_problem b/counting_problem @@ -9,7 +9,7 @@ - [counting_query_answers] - [counting_cqs] - For [satisfiability_boolean]: [sharp_satisfiability] -- [counting_simple_path]s +- [counting_simple_paths] - [sharp_automaton]: - [sharp_nfa], cf [arenas2020efficient] - [sharp_ufa] diff --git a/craig_interpolation b/craig_interpolation @@ -1,6 +1,6 @@ # Craig interpolation -For every [implication] φ => ψ, there is a formula χ using only the common [relation_symbol]s of φ and ψ such that φ => χ and χ => ψ +For every [implication] φ => ψ, there is a formula χ using only the common [relation_symbols] of φ and ψ such that φ => χ and χ => ψ - [cate2023craig]: [survey_article] on [craig_interpolation] for [guarded_fragment] - [cate2024craig]: [invited_talk] diff --git a/database_dependency b/database_dependency @@ -1,6 +1,6 @@ # Dependency (databases) -An [implication] in [first_order_logic] with [universal_quantifier]s and with a [conjunction] of [atom] on the left-hand-side +An [implication] in [first_order_logic] with [universal_quantifiers] and with a [conjunction] of [atom] on the left-hand-side ## Terminology @@ -16,7 +16,7 @@ An [implication] in [first_order_logic] with [universal_quantifier]s and with a ## Generalization - [disjunctive_dependency] - - [disjunctive_tuple_generating_dependency]: right hand side is [disjunction] of [conjunction] of [atom]s + - [disjunctive_tuple_generating_dependency]: right hand side is [disjunction] of [conjunction] of [atoms] ## Problems diff --git a/densest_subgraph b/densest_subgraph @@ -4,9 +4,9 @@ https://en.wikipedia.org/wiki/Dense_subgraph Find subgraph of maximal density (#edges/#vertices) of input graph -- Goldberg's algorithm: This is in [ptime] and reducible to [network_flow] - - Lien avec [submodularity]/[supermodularity], cf [chekuri2022densest] -- Also a [greedy_algorithm] (Charikar's algorithm) +- [Goldberg's_algorithm]: This is in [ptime] and reducible to [network_flow] + - Connection to [submodularity] / [supermodularity], cf [chekuri2022densest] +- Also a [greedy_algorithm]: [Charikar's_algorithm] - Efficient algorithms on some graph classes, e.g., [harpeled2024approximating] Up: [graph] diff --git a/diagram b/diagram @@ -6,7 +6,7 @@ - [nobdd] - [fbdd] - [nrobp] - - generalization [read_k_branching_program]s + - generalization [read_k_branching_programs] - like [k_ambiguous] - cf [jukna1995note] - [bdd_subfunction] for [subfunction] diff --git a/dual_graph b/dual_graph @@ -1,8 +1,8 @@ # Dual graph [graph_undirected]: -- vertices are [clause]s -- edges connect two clauses that share a variable +- [vertices] are [clauses] +- [edges] connect two [clauses] that share a [variable] if [conjunctive_normal_form] has unbounded [degree] then contains a large [clique] diff --git a/equation b/equation @@ -1,6 +1,7 @@ # Equation - [word_equation] +- [semigroup_equation] - [semiring_equation] - [polynomial_equation] - [diophantine_equation] @@ -10,3 +11,5 @@ Up: [mathematics] See also: [disequation], [inequation], [equality], [left_hand_side], [right_hand_side] + +Aliases: equations diff --git a/graph_database_practical b/graph_database_practical @@ -10,7 +10,7 @@ Query languages: Models: -- [Property_graph]s: nodes and directed edges which have an ID and takes a value from some property +- [Property_graphs]: nodes and directed edges which have an ID and takes a value from some property Up: [graph_database] diff --git a/graph_packing b/graph_packing @@ -1,6 +1,6 @@ # Graph packing -A [packing_problem] in [graph]s +A [packing_problem] in [graphs] E.g., [path], [triangle], etc. diff --git a/graph_partition b/graph_partition @@ -1,6 +1,6 @@ # Graph partition -splitting a [graph] into [connected_component]s with prescribed size +splitting a [graph] into [connected_components] with prescribed size [graph_partition_hardness] diff --git a/guarded_structure b/guarded_structure @@ -1,7 +1,7 @@ # Guarded structure A guarded [structure] is a [structure] S where either: -- all [relation]s are empty or +- all [relations] are empty or - there is a [relation] and a [fact] F (called "guard") such that - the [active_domain] of F is the [active_domain] of S diff --git a/incidence_graph b/incidence_graph @@ -1,8 +1,8 @@ # Incidence graph [graph_bipartite]: -- left vertices are [variable]s -- right vertices are [clause]s +- left vertices are [variables] +- right vertices are [clauses] - edge connects variable to clause if variable occurs in clause Up: [graph_bipartite], [conjunctive_normal_form] diff --git a/linear_programming b/linear_programming @@ -1,11 +1,11 @@ # Linear programming minimize c^t x st A^t x = b and x >= 0 pointwise -- [dual] problem: [variable]s y dans R^d, cost b, we want to minimize b^t y +- [dual] problem: [variables] y dans R^d, cost b, we want to minimize b^t y - and A y \geq c, defines a [polytope] - so we want to find the point inside the polytope which minimizes the cost -[algorithm]s (cf [aaron_sidford_talk]): +[algorithms] - [simplex_algorithm], fast in practice but slow in memory - [ellipsoid], moderate in both - [interior_point] methods, it's the best in practice diff --git a/longest_parameterized_common_subsequence b/longest_parameterized_common_subsequence @@ -1,6 +1,6 @@ # Longest parameterized common subsequence -[longest_common_subsequence] with [parameter]s of various kinds, cf [iliopoulos2007algorithms] for instance +[longest_common_subsequence] with [parameters] of various kinds, cf [iliopoulos2007algorithms] for instance apparently also under [alphabet_bijection], cf [parameterized_matching], in [keller2009longest] diff --git a/markovs_inequality b/markovs_inequality @@ -2,7 +2,7 @@ https://en.wikipedia.org/wiki/Markov%27s_inequality -For a nonnegative random variable X, the probability that it is at least a>0 is no greater than E[X]/a. +For a nonnegative random variable X, the probability that it is at least a>0 is no greater than E[X ]/a. Indeed, when X geq a it contributes at least a to the expectation, and otherwise it contributes at least zero. diff --git a/minimum_unsatisfiable_core b/minimum_unsatisfiable_core @@ -2,7 +2,7 @@ A subset of the [clauses] of a [CNF] [Boolean_formula] which is [unsatisfiable] and has a [minimum] number of clauses -It is [sigmap2]_complete to compute +It is [sigma_p_2_complete] to compute - https://cstheory.stackexchange.com/questions/54692/complexity-of-computing-minimum-unsatisfiable-core [umans1999hardness] diff --git a/morphism b/morphism @@ -1,6 +1,6 @@ # Morphism -on [word]s +On [words]: - [non_erasing_morphism] - [length_preserving_morphism] diff --git a/nbp b/nbp @@ -2,10 +2,9 @@ Like [nrobp] but without the "free" aspect (cf [fbdd]). -Other name: nFBDD - -It is shown in meinel1989nondeterministic to be as powerful as [nptime] and so -we can translate [circuit] to NBPs in [ptime] -- the key argument is to use the [tseitsin_transform] +It is shown in [meinel1989nondeterministic] to be as powerful as [nptime] and so we can translate [circuits] to NBPs in [ptime] +- the key argument is to use the [tseytin_transform] Up: [diagram] + +Aliases: NBPs diff --git a/np_complete b/np_complete @@ -20,10 +20,7 @@ Problem which is in [nptime] and [np_hard] weakly NP-complete ou [strongly_np_complete] depending on whether there exist [pseudo_polynomial_time] algorithms -different notions of [reduction]? -- it is open whether [np_complete] problems under [logspace_reductions] and [ptime_reduction] are different - - cf https://en.wikipedia.org/wiki/Log-space_reduction - - of course [Turing_reductions] and [Karp_reductions] give a different notion because they may identify [NP] and [coNP] +different notions of [reduction]: cf [np_definition_reductions] Up: [completeness] for [nptime] diff --git a/np_hard b/np_hard @@ -1,11 +1,8 @@ # NP-hard -at least as hard as the hardest [computational_problem]s in [nptime] +at least as hard as the hardest [computational_problems] in [nptime] - admits a [ptime_reduction] from any [nptime] problem -- subtlety about which type of reduction is allowed, e.g., [many_one_reduction] vs [turing_reduction] - - usual notion is [many_one_reduction] - - with [turing_reduction], the difference between [np] and [conp] disappears - - https://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc +- subtlety about which type of [reduction] is allowed: [np_definition_reduction] See also: [nptime], [computational_hardness] diff --git a/omqa b/omqa @@ -1,7 +1,7 @@ # Ontology-Mediated Query Answering (OMQA) definition: -- given an [instance] I and [query] Q and [logical_constraint]s Sigma +- given an [instance] I and [query] Q and [logical_constraints] Sigma - does every [superinstance] of I satisfying Sigma also satisfy Q? subtlety: [omqa_finite] vs [omqa_unrestricted] diff --git a/pattern_matching b/pattern_matching @@ -28,8 +28,8 @@ - [two_way_string_matching] - [regular_expression] - [pattern_with_variables] -- [pattern_matching_wildcards] when allowing [wildcard]s -- [pattern_matching_dontcare] when allowing [dontcare]s (one single symbol can be anything) +- [pattern_matching_wildcards] when allowing [wildcards] +- [pattern_matching_dontcare] when allowing [dontcares] (one single symbol can be anything) - [pattern_matching_compressed] on [compressed_data] - [gapped_pattern_matching]: find two patterns separated by a distance within a specified range diff --git a/probabilistic_method b/probabilistic_method @@ -1,6 +1,6 @@ # Probabilistic method -- farago2021meeting +- [farago2021meeting] - [lovasz_local_lemma] diff --git a/satisfiability_weighted_obdds b/satisfiability_weighted_obdds @@ -1,9 +0,0 @@ -# Satisfiability weighted obdds - -Can do [satisfiability_weighted] for [OBDDs] by [product_construction] in the case of [unary] weights - -Also following [topological_sort], cf <2jzxunmsdpibv6fugq7ea2hynubogjv23hodoeht3zvkarqrnn@sehlj2lzwszy> - -Up: [satisfiability_weighted_knowledge_compilation], [satisfiability_weighted], [obdd] - -Aliases: satisfiability weighted obdd diff --git a/separator_logic b/separator_logic @@ -2,7 +2,7 @@ [first_order_logic] with a predicate talking about the existence of a path (see [reachability], [transitive_closure]) while avoiding certain vertices -See bojanczyk2021separator +See [bojanczyk2021separator] Between [first_order_logic] and [monadic_second_order_logic] diff --git a/sharp_ufa b/sharp_ufa @@ -2,7 +2,7 @@ given [word_automaton_unambiguous] A and length n in [unary], count the number of words of length n accepted by A -in [ptime], by counting [run]s +in [ptime], by counting [runs] even if n is given in binary, by [fast_exponentiation] and [matrix_multiplication] - cf https://cstheory.stackexchange.com/a/8202 diff --git a/spanner b/spanner @@ -22,7 +22,7 @@ ## Formalisms -- [regex_formula]s +- [regex_formulas] - [variable_set_automaton] - can be extended with - [relational_algebra] diff --git a/spanner_core b/spanner_core @@ -1,8 +1,8 @@ # Spanner core -[regex_formula]s extended with [projection], [union], [join], and [string_equality_selection] +[regex_formulas] extended with [projection], [union], [join], and [string_equality_selection] -Other way to see it: [query] over the result of [spanner]s +Other way to see it: [query] over the result of [spanners] ([freydenberger2018joining] / [peterfreund2019complexity]) Extension: [generalized_core_spanner] diff --git a/spanner_regular b/spanner_regular @@ -2,7 +2,7 @@ two equivalent definitions ([peterfreund2019complexityb] section 2.4): - with [variable_set_automaton] -- with [regex_formula]s extended with [union], [projection], and [join] +- with [regex_formulas] extended with [union], [projection], and [join] - optionally with [difference] Up: [spanner] diff --git a/subset_sum b/subset_sum @@ -7,7 +7,7 @@ given integers S and a target t, can we achieve t exactly as a sum of a subset o special case: [partition_problem] -[reduction]s: +[reductions]: - [reduction_sat_subset_sum] from [satisfiability_boolean] on [conjunctive_normal_form] - [reduction_3dm_subset_sum] from [3_dimensional_matching] diff --git a/subword_automaton b/subword_automaton @@ -1,6 +1,6 @@ # Subword automaton -[Automaton] that accepts the language of the [subwords] of [word]s accepted by another [automaton] +[Automaton] that accepts the language of the [subwords] of [words] accepted by another [automaton] - given an [automaton], can build subword automaton as [automata_nondeterministic] - cf [karandikar2014state] Section 3.1 diff --git a/theoretical_computer_science b/theoretical_computer_science @@ -32,7 +32,7 @@ - agregator https://cstheory-feed.org/ - list of [blog] https://rjlipton.wpcomstaging.com/2022/01/26/a-list-of-most-theory-blogs/ - descriptive resources https://cstheory.stackexchange.com/questions/36436/where-to-learn-more-about-what-theoretical-computer-science-is -- wigderson2019mathematics +- [wigderson2019mathematics] ## Questions diff --git a/transitivity_tgds b/transitivity_tgds @@ -2,9 +2,8 @@ Results on transitivity: -- amarilli2018query -- andrew2021guarded, which discusses amarilli2018query in detail -- baget2015combining, problem with a weird condition for transitivity plus [linear_rules] ([existential_rule]) - - question: link to feller2022finite? +- [amarilli2018query] +- [andrew2021guarded], which discusses [amarilli2018query] in detail +- [baget2015combining], problem with a condition for transitivity plus [linear_rules] ([existential_rule]) Up: [transitivity] for [open_world_query_answering] diff --git a/tseytin_transformation b/tseytin_transformation @@ -5,3 +5,5 @@ https://en.wikipedia.org/wiki/Tseytin_transformation Transform a [Boolean_circuit] into [equisatisfiable] [CNF], by adding some additional [variables] Up: [circuit] + +Aliases: Tseytin transform diff --git a/turing_machine b/turing_machine @@ -4,7 +4,7 @@ [petersen2008sorting]: bounds on complexity of [sorting] - [turing_machine_deterministic] vs [turing_machine_nondeterministic] -- one or more work [tape]s (and read-only input) +- one or more work [tapes] (and read-only input) ## Types diff --git a/tuzas_conjecture b/tuzas_conjecture @@ -2,6 +2,6 @@ https://en.wikipedia.org/wiki/Tuza%27s_conjecture -[Conjecture] about [graph_packing] of [triangle]s +[Conjecture] about [graph_packing] of [triangles] Up: [graph_packing] diff --git a/van_emde_boas_tree b/van_emde_boas_tree @@ -1,7 +1,6 @@ # Van Emde Boas tree -[fully_persistent] and generalization -https://dl.acm.org/doi/abs/10.1145/2483699.2483702?casa_token=ev35wNcpOZkAAAAA:yriGm4Tcy1xmJeiSZcCg6WToRRv2rtA0htk15dAuzAhJkNpFkAGQ0aAYZpWG17gz-KYcOWD1sOgiCg +[fully_persistent] and generalization: [chan2013persistent] - used for [twin_width] in [gajarsky2022twin] - used for [predecessor_problem] and [colored_predecessor] diff --git a/variety b/variety @@ -2,9 +2,9 @@ ## Variety of formal language -Variety of [formal_language]s is closed under: +Variety of [formal_languages] is closed under: - [Derivative] -- [Boolean_operator]s ([union], [intersection], [complementation]) +- [Boolean_operators] ([union], [intersection], [complementation]) - maybe not [complementation] in which case it is a [positive_variety] - and [inverse_morphism] @@ -14,10 +14,10 @@ Variety of [monoid] is closed under [direct_product], [quotient], and [submonoid ## Variety of [semigroup] -We can impose that some elements in [equation]s are not mapped to the [neutral_element] +We can impose that some elements in [semigroup_equations] are not mapped to the [neutral_element] - cf [non_erasing_morphism] -## Variety of [stamp]s +## Variety of [stamps] - cf [length_preserving_morphism] diff --git a/walk_length b/walk_length @@ -6,7 +6,7 @@ Given [graph_directed], G, [source] s, [sink] t, length l, decide if there is a - if l is given as input in unary, the problem is tractable by creating l copies of G - O(l |G|) - [fine_grained_complexity] bounds, cf [nfa_unary_lengths] -- if l is given in binary, the problem is [ptime] by [fast_exponentiation] to get the possible lengths of [walk]s in log l +- if l is given in binary, the problem is [ptime] by [fast_exponentiation] to get the possible lengths of [walks] in log l - O(log l |G|) - if the edges of G can be annotated with lengths also written in binary - [np_hard] by reduction from [subset_sum]