commit 6351deef3e0951e493be347c97eca2642db6ade5 parent f3f99b7248db696abacabf972ef78cd695337e53 Author: Antoine Amarilli <a3nm@a3nm.net> Date: Sat, 5 Sep 2026 15:04:14 +0200 commit with codex Diffstat:
83 files changed, 122 insertions(+), 90 deletions(-)
diff --git a/4_partition_hardness_proof b/4_partition_hardness_proof @@ -1,4 +1,4 @@ -# 4_partition_hardness_proof +# 4 partition hardness proof Proof in http://courses.csail.mit.edu/6.890/fall14/6046-L16.pdf reduction from [3_dimensional_matching] diff --git a/abokhamis2024fast b/abokhamis2024fast @@ -1,4 +1,4 @@ -# Abokhamis2024fast +# abokhamis2024fast [academic_paper] by [mahmoud] and [dan_suciu] and [xiao_hu] diff --git a/ackermanns_function b/ackermanns_function @@ -1,4 +1,4 @@ -# Ackermanns_function +# Ackermann's function [ackermanns_function_unary] diff --git a/akmal2021majority b/akmal2021majority @@ -1,4 +1,4 @@ -# Akmal2021majority +# akmal2021majority about [maj_sat] and [gt_maj_sat] diff --git a/approximation b/approximation @@ -12,7 +12,7 @@ Complexity classes [approximation_class]: Problems: [approximation_problems] Reasons not to get it: -- conditional inapproximability [fpras_vs_npc]: no [FPRAS] if the [decision_problem] "décision =0" is [np_hard], unless you have [nptime] = [bpp] or [nptime] = [rp] +- conditional inapproximability [fpras_vs_npc]: no [FPRAS] if the [decision_problem] "decision =0" is [np_hard], unless you have [nptime] = [bpp] or [nptime] = [rp] - [sharp_is]: no [FPRAS] to count the [independent_sets] of a [graph] - no [FPRAS] for [monotone2cnf] ([calautti2022query]), cf [sharp_satisfiability_fpras] - [hardness_of_approximation] diff --git a/approximation_algorithm b/approximation_algorithm @@ -0,0 +1,7 @@ +# Approximation algorithm + +- [Christofides_heuristic] + +Up: [approximation_problem], [algorithm] + +Aliases: approximation algorithms diff --git a/approximation_problem b/approximation_problem @@ -1,8 +1,10 @@ -# Approximation algorithm +# Approximation problem - [all_pairs_shortest_path_approximate] - [sharp_satisfiability_approximate] -See also: [fpras] +See also: [fpras], [approximation_algorithm] Up: [computational_problem] for [approximation] + +Aliases: approximation problems diff --git a/arithmetic_circuit b/arithmetic_circuit @@ -11,7 +11,7 @@ Conditions: - [deterministic] - [smoothness] / [smoothing] -Arithmetic circuits *with positive weights* can be translated to a [boolean_circuit] while preserving struural restrictions. Thus, for arithmetic functions whose support is a hard boolean function, we can leverage lower bounds on the [boolean_circuit] size to get a bound on the arithmetic circuit size +Arithmetic circuits *with positive weights* can be translated to a [boolean_circuit] while preserving structural restrictions. Thus, for arithmetic functions whose support is a hard boolean function, we can leverage lower bounds on the [boolean_circuit] size to get a bound on the arithmetic circuit size Can use [rank] technique for lower bound, using [communication_complexity] - but [arithmetic_rectangle] instead of [combinatorial_rectangle] diff --git a/automaton_primality b/automaton_primality @@ -2,7 +2,7 @@ decide if an input DFA can be written as the [automaton_intersection] of input DFAs that all have strictly less states -it in [NP_hard] to decide, see [spenner2026deciding] +it is [NP_hard] to decide, see [spenner2026deciding] other related article: [jecker2020unary] diff --git a/backurs2016which b/backurs2016which @@ -1,4 +1,4 @@ -# Backurs2016which +# backurs2016which lower bound using [strong_exponential_time_hypothesis] and [orthogonal_vectors] diff --git a/bag_semantics b/bag_semantics @@ -1,6 +1,6 @@ # Bag semantics -The [query_semantics] where [queries] result results with [duplicates], i.e., a [multiset] +The [query_semantics] where [queries] results have [duplicates], i.e., a [multiset] Up: [query_semantics] diff --git a/benameur2024complexity b/benameur2024complexity @@ -1,4 +1,4 @@ -# Benameur2024complexity +# benameur2024complexity about [hunters_and_rabbit_directed] diff --git a/benameur2024cops b/benameur2024cops @@ -1,4 +1,4 @@ -# Benameur2024cops +# benameur2024cops they study [hunters_and_rabbit_directed] diff --git a/berkholz2017answering b/berkholz2017answering @@ -1,4 +1,4 @@ -# Berkholz2017answering +# berkholz2017answering "Answering Conjunctive Queries under Updates" diff --git a/bonifati2017analytical b/bonifati2017analytical @@ -1,4 +1,4 @@ -# Bonifati2017analytical +# bonifati2017analytical inspired [martens2018evaluation] diff --git a/boolean_function_representation b/boolean_function_representation @@ -8,3 +8,5 @@ A [formalism] that represents a [Boolean_function] - [knowledge_compilation_classes] Up: [formalism] for [Boolean_function] + +Aliases: Boolean function representations diff --git a/buchbinder2019simple b/buchbinder2019simple @@ -1,4 +1,4 @@ -# Buchbinder2019simple +# buchbinder2019simple [approximation], [multiway_cut] diff --git a/carmeli2023conjunctive b/carmeli2023conjunctive @@ -1,4 +1,4 @@ -# Carmeli2023conjunctive +# carmeli2023conjunctive [academic_paper] by [luc_segoufin] and [nofar] about [enumeration_self_joins] diff --git a/chen2010constraint b/chen2010constraint @@ -1,4 +1,4 @@ -# Chen2010constraint +# chen2010constraint [academic_paper] by [hubie_chen] and [martin_grohe] diff --git a/circuit_classes b/circuit_classes @@ -6,7 +6,7 @@ In [circuit_complexity]: - [ac] AC, [ac0], etc. - [tc] TC, [tc0], etc. - [acc] ACC, [acc0], etc. - - liens avec [solvable_group] + - links with [solvable_group] In [knowledge_compilation]: see [knowledge_compilation_classes] diff --git a/complexity_space b/complexity_space @@ -1,4 +1,4 @@ -# Complexity_space +# Space complexity - [savitchs_theorem]: we can simulate [nondeterministic] machine with [quadratic] blowup in space diff --git a/complexity_time_classes b/complexity_time_classes @@ -1,5 +1,7 @@ # Complexity time classes +https://en.wikipedia.org/wiki/Time_complexity + - [ptime] / [p_complete] - [linear_time], [linear_time_nearly], [linear_time_almost] - [np_intermediate], cf [ladners_theorem] diff --git a/computational_complexity b/computational_complexity @@ -50,7 +50,6 @@ ## Resources -- valeurs possibles sur wikipedia: en.wikipedia.org/wiki/Time_complexity - [descriptive_complexity] - [lower_bounds] - [klees_measure_problem] diff --git a/computer_algebra b/computer_algebra @@ -1,7 +1,7 @@ # Computer algebra - [grobner_basis], seems useful to solve [polynomial_equation] -- matrixcalculus.org, calculs matriciels (différentiation etc) +- matrixcalculus.org, matrix calculations (differential etc) - https://chadnauseam.com/coding/random/calculator-app on computer algebra for a calculator app: - [bignum] - [rationals] diff --git a/conjunctive_query_acyclic b/conjunctive_query_acyclic @@ -9,7 +9,7 @@ the evaluation problem is in the complexity class [logcfl], and the complexity i We can test in linear time if a [hypergraph] is acyclic and if so build the [join_tree]: [GYO_algorithm] - not so obvious to understand where the [linear_time] claim comes from... -For Boolean queries, even with [self_joins], if the query is not acyclic then we can reduce from a hard problem ([triangle_detection] ou [hyperclique_detection]) +For Boolean queries, even with [self_joins], if the query is not acyclic then we can reduce from a hard problem ([triangle_detection] or [hyperclique_detection]) Special case: [conjunctive_query_hierarchical] diff --git a/context_free_grammar_deterministic b/context_free_grammar_deterministic @@ -1,4 +1,4 @@ -# Deterministic Context free grammar +# Deterministic Context Free Grammar [CFG] accepted by [pushdown_automaton_deterministic] @@ -6,6 +6,6 @@ no good intrinsic formulation in terms of [CFGs] Up: [context_free_grammar], [determinism] -Aliases: DCFG, DCFGs, deterministic CFG, deterministic CFGs +Aliases: DCFG, DCFGs, deterministic CFG, deterministic CFGs, Deterministic Context Free Grammar, Deterministic Context-Free Grammar See also: [context_free_language_deterministic], [DPDA] diff --git a/context_free_language_reachability b/context_free_language_reachability @@ -7,3 +7,5 @@ Can be solved in [cubic] time [bringmann2024nfa] [Subcubic_equivalent] to [2NPDA_acceptance] Up: [computational_problem], [graph], [CFGs] + +Aliases: Context free reachability diff --git a/datalog_negation b/datalog_negation @@ -1,7 +1,7 @@ # Datalog negation Semantics problem: [negation_semantics] -- because [Datalog_inference] it is no longer [monotone] +- because [Datalog_inference] is no longer [monotone] Simple solution: [negation_stratified], i.e., adding [negation] only to [datalog_stratified], with negations on predicates of lower [Datalog_stratum] diff --git a/degeneracy b/degeneracy @@ -17,7 +17,7 @@ The [arboricity] is no greater than the degeneracy, and the degeneracy is at mos The degeneracy of an [undirected_graph] is equal to the [maximum_degree] if and only if one of the [connected_components] is a [regular_graph] https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#Examples -A [k_vertex_connected] graph has degeneracy at most k +A [k_vertex_connected] graph has degeneracy at least k Up: [width_measure] diff --git a/degree b/degree @@ -2,7 +2,7 @@ Number of [neighbors] of a [vertex] -In [directed_graphs], we can distinguish the [indegree] and [outdegree], respectively the number of [vertices] having a edge to the [vertex], or from the [vertex] +In [directed_graphs], we can distinguish the [indegree] and [outdegree], respectively the number of [vertices] having an edge to the [vertex], or from the [vertex] - [maximal_degree] - [average_degree] diff --git a/deletion_propagation b/deletion_propagation @@ -1,6 +1,6 @@ # Deletion propagation -Find the minimal set of [facts] to delete from a [database] so that the query result in changed in a certain way +Find the minimal set of [facts] to delete from a [database] so that the query result is changed in a certain way - [generalized_deletion_propagation], cf [deletion_propagation] - [deletion_propagation_with_source_side_effects] diff --git a/dimension b/dimension @@ -5,3 +5,5 @@ - [vc_dimension] Up: [mathematics] + +Aliases: dimensions diff --git a/distance b/distance @@ -9,3 +9,5 @@ Up: [mathematics] See also: [metric_space] + +Aliases: distances diff --git a/domain_element b/domain_element @@ -3,3 +3,5 @@ A *domain element* is an element of the [domain] of a [structure] or of a [relational_instance] Up: [logic] + +Aliases: domain elements diff --git a/fagin1983degrees b/fagin1983degrees @@ -1,13 +1,7 @@ -# Degree of acyclicity +# fagin1983degrees -- [alpha_acyclic] -- [beta_acyclic] - - [lanzinger2021tractability] -- [gamma_acyclic] -- [berge_acyclic] +discusses [hypergraph_acyclicity] Up: [academic_paper] about [hypergraph_acyclicity] See also: [gyo], [brault2014hypergraph] - -Aliases: degree of acyclicity diff --git a/free_variable b/free_variable @@ -3,3 +3,5 @@ A [variable] to which no [quantifier] apply, e.g., part of the output of a [query] Up: [variable] + +Aliases: free variables diff --git a/ganian2022weighted b/ganian2022weighted @@ -1,4 +1,4 @@ -# Ganian2022weighted +# ganian2022weighted https://arxiv.org/abs/2206.01706 diff --git a/graph_query_languages b/graph_query_languages @@ -13,7 +13,7 @@ Theoretical languages: - like [xpath] - [regular_query]: - binary non-recursive [datalog] with [transitive_closure] of binary predicates - - captures [nested_regular_expressions] et [uc2rpq] + - captures [nested_regular_expressions] and [UC2RPQs] - [Conjunctive_context_free_path_query] - [Regular_queries_with_memory] - [SPARQL] diff --git a/han2008generalizations b/han2008generalizations @@ -1,4 +1,4 @@ -# Han2008generalizations +# han2008generalizations contains [paper_bug] because depends on wrong statement, according to [caron2017hierarchy] diff --git a/heimberg2016hanf b/heimberg2016hanf @@ -1,5 +0,0 @@ -# Heimberg2016hanf - - - -Up: [academic_paper] about [hanf_normal_form] for [fo_mod] diff --git a/hu2023finding b/hu2023finding @@ -1,4 +1,4 @@ -# Hu2023finding +# hu2023finding [academic_paper] on [minimal_witness] diff --git a/hu2024output b/hu2024output @@ -1,4 +1,4 @@ -# Hu2024output +# hu2024output [Academic_paper] on the complexity of [yannakakis_algorithm] diff --git a/hypergraph_acyclicity b/hypergraph_acyclicity @@ -14,3 +14,5 @@ Up: [graph_acyclicity], [hypergraph] See also: [graph_traversal] + +Aliases: degrees of acyclicity, degree of acyclicity diff --git a/ilango2022minimum b/ilango2022minimum @@ -1,4 +1,4 @@ -# Illango2022minimum +# illango2022minimum [academic_paper] about [minimum_formula_size_problem] diff --git a/im2024convergence b/im2024convergence @@ -1,4 +1,4 @@ -# Im2024convergence +# im2024convergence [academic_paper] at [ICDT_2024] about [convergence] of [datalog] diff --git a/independent_set b/independent_set @@ -12,7 +12,7 @@ An *independent set* is a [subset] of [vertices] of an [undirected_graph] such t ## Variants -- [maximum_independent_set]: [np_hard] to find, mais [ptime] in [graph_bipartite] ([maximum_independent_set_bipartite]) +- [maximum_independent_set]: [NP_hard] to find, but [PTIME] in [graph_bipartite] ([maximum_independent_set_bipartite]) - [maximal_independent_set]: [ptime] to find with [greedy_algorithm] - [generalized_dominating_set] - [independent_set_enumeration] diff --git a/locally_threshold_testable_language b/locally_threshold_testable_language @@ -1,4 +1,4 @@ -# Locally_threshold_testable_language +# Locally threshold testable language Discussed in [bojanczyk2007new] diff --git a/logic_atom b/logic_atom @@ -1,6 +1,6 @@ # Logic atom -"Atom book" de [bojanczyk]: https://www.mimuw.edu.pl/~bojan/paper/atom-book +"Atom book" by [bojanczyk]: https://www.mimuw.edu.pl/~bojan/paper/atom-book [bojanczyk2019slightly] Up: [atom] diff --git a/makowsky2003tree b/makowsky2003tree @@ -1,4 +1,4 @@ -# Makowsky2003tree +# makowsky2003tree Proposition 32 shows that there are graphs with high [treewidth], even [subdivision] of [grid_graph], on which [monadic_second_order_logic] evaluation is in [ptime] diff --git a/martens2018evaluation b/martens2018evaluation @@ -1,4 +1,4 @@ -# Martens2018evaluation +# martens2018evaluation introduced [simple_transitive_expressions] diff --git a/marx2020four b/marx2020four @@ -1,4 +1,4 @@ -# Marx2020four +# marx2020four - [bidimensionality] - [maximum_independent_set], beating the naive exponential algorithm diff --git a/negation_normal_form b/negation_normal_form @@ -1,6 +1,6 @@ # Negation normal form -[Boolean_circuits] using [OR], [AND], [literal_gates], and [cosntant_gates] +[Boolean_circuits] using [OR], [AND], [literal_gates], and [constant_gates] Hence, [negation] is only at the leaves diff --git a/np_complete b/np_complete @@ -17,8 +17,8 @@ Problem which is in [nptime] and [np_hard] - [minimum_vertex_cover] - [maximum_independent_set] -weakly NP-complete ou [strongly_np_complete] depending on whether there exist -[pseudo_polynomial_time] algorithms +weakly NP-complete or [strongly_NP_complete] depending on whether there exist +[pseudo_polynomial_time] [algorithms] different notions of [reduction]: cf [np_definition_reductions] diff --git a/query_boolean b/query_boolean @@ -2,7 +2,7 @@ A [query] whose [query_answer] is a [Boolean]: either the query holds or it does not. -For [queries] with [free_variables] that are [first_order], the [computational_complexity] of computing [query_answers] is often [PTIME]-equivalent to the Boolean queries obtained by considering each of the polynomially many possible answers and creating a Boolean query by insantianing these [variables] to [constants] +For [queries] with [free_variables] that are [first_order], the [computational_complexity] of computing [query_answers] is often [PTIME]-equivalent to the Boolean queries obtained by considering each of the polynomially many possible answers and creating a Boolean query by instantiating these [variables] to [constants] In [logic], this is called a [sentence] diff --git a/rabin1963probabilistic b/rabin1963probabilistic @@ -1,4 +1,4 @@ -# Rabin1963probabilistic +# rabin1963probabilistic [academic_paper] by [rabin] diff --git a/radoszewski2011hamiltonian b/radoszewski2011hamiltonian @@ -1,4 +1,4 @@ -# Radoszewski2011hamiltonian +# radoszewski2011hamiltonian Studies when the [graph_square] of an [undirected_graph] has [Hamiltonian_cycle] and [Hamiltonian_path] diff --git a/random_variable b/random_variable @@ -8,3 +8,5 @@ Can take several values, each of which is called a [probability_outcome] Up: [probabilities] See also: [correlation] + +Aliases: random variables diff --git a/regular_expression_denial_of_service b/regular_expression_denial_of_service @@ -1,4 +1,4 @@ -# Regular_expression_denial_of_service (ReDoS) +# Regular expression denial of service (ReDoS) Caused in particular by [backtracking] diff --git a/regular_expression_deterministic b/regular_expression_deterministic @@ -1,7 +1,7 @@ # Deterministic regular expression, aka "one-unambiguous" - position automaton is [automata_deterministic] - - aussi [glushkov_automaton] is [automata_deterministic] + - also [glushkov_automaton] is [automata_deterministic] [groz2012deterministic] and [groz2017efficient] - can check in [linear_time] if [regular_expression] is deterministic diff --git a/regular_language b/regular_language @@ -33,7 +33,7 @@ - [star_height] - arbitrarily large - connection to [cycle_rank] of [automata] via [eggans_theorem] -- [generalized_star_height] en ajoutant [complementation] +- [generalized_star_height] by adding [complementation] - generalized star height of zero is [star_free_language] - [state_complexity] - [syntactic_complexity] diff --git a/repetitive_string b/repetitive_string @@ -5,3 +5,5 @@ A [word] containing a nonempty [square_word] as a [factor] Up: [square_word] See also: [square_free_word], [repetitive_string_language] + +Aliases: repetitive strings diff --git a/representation b/representation @@ -6,3 +6,5 @@ - [pseudo_boolean_constraint] Up: [mathematics] + +Aliases: representations diff --git a/right_extension b/right_extension @@ -5,3 +5,5 @@ A [word] u is a *right extension* of a [word] v iff v is a [prefix] of u Up: [prefix] See also: [distinguishing_extension], [extension] + +Aliases: right extensions diff --git a/semigroup b/semigroup @@ -13,3 +13,5 @@ Examples: - [syntactic_semigroup] Up: [mathematics_basic_concepts] + +Aliases: semigroups diff --git a/set_cover_red_blue b/set_cover_red_blue @@ -4,7 +4,7 @@ cf [carr2000red] You have a universe where some elements are red and others are blue -You have a collection of sets and want to find a subfamily that covers all blue elements but covers a least number of red elements +You have a collection of sets and want to find a subfamily that covers all blue elements but covers the least number of red elements The question is how well can it be [approximated], compared to [set_cover_approximation] diff --git a/set_theory b/set_theory @@ -1,4 +1,4 @@ -# Set_theory +# Set theory - [set] diff --git a/shapley_value b/shapley_value @@ -14,7 +14,7 @@ Results: - connections with [model_counting] and [pqe] - [bienvenu2023when] - [kara2023from] -- [standke2025tractability] pour [CQ_aggregates], when is is tractable depending on the [aggregation_function] and the [CQ] shape ([hierarchical_queries], [q_hierarchical_queries]) +- [standke2025tractability] for [CQ_aggregates], when is is tractable depending on the [aggregation_function] and the [CQ] shape ([hierarchical_queries], [q_hierarchical_queries]) - [shapley_value_omqa] diff --git a/simple_path_parity_problem b/simple_path_parity_problem @@ -6,6 +6,6 @@ This is [NP_complete] in general graphs by reduction from [two_disjoint_simple_p But on [planar_graphs] it is in [PTIME] by [nedev1999finding] - shown by reduction to [undirected_k_disjoint_path_problem] -- also and on [outerplanar_graphs] it is in [PTIME] even for [simple_path_RPQ] by [nedev2000polynomial] +- also on [outerplanar_graphs] it is in [PTIME] even for [simple_path_RPQ] by [nedev2000polynomial] Up: [simple_path_problem] diff --git a/spanning_subgraph b/spanning_subgraph @@ -0,0 +1,8 @@ +# Spanning subgraph + +A *spanning subgraph* is a [subgraph] containing all the vertices of the original graph + +- [spanning_tree] +- [k_factor] + +Up: [subgraph] diff --git a/square_free_word b/square_free_word @@ -1,6 +1,6 @@ # Square free word -A [word] which does not contain a nonempty [factor] which is a [square], i.e.,a [word] which is not a [repetitive_string] +A [word] which does not contain a nonempty [factor] which is a [square], i.e., a [word] which is not a [repetitive_string] There are infinite square-free words over a ternary alphabet diff --git a/structure b/structure @@ -15,4 +15,4 @@ Up: [logic] See also: [relational_instance], [structuredness] -Aliases: structure (logic) +Aliases: structure (logic), structures diff --git a/submodular_set_function b/submodular_set_function @@ -12,3 +12,5 @@ Special case discussed in [zivny2009expressive]: [submodular_set_function_bounde See also: [submodular_optimization], [concave_function] Up: [submodular_function] + +Aliases: submodular set functions diff --git a/tree_decomposition_updating b/tree_decomposition_updating @@ -1,7 +1,7 @@ # Updating tree decomposition - [korhonen2023dynamic] -- [gottlob2022incremental], sur [generalized_hypertree_decomposition] +- [gottlob2022incremental], on [generalized_hypertree_decomposition] Up: [incremental_maintenance] of [tree_decomposition] diff --git a/treewidth_directed b/treewidth_directed @@ -1,10 +1,12 @@ -# Treewidth (directed) +# Directed treewidth directed treewidth, when it is bounded then the k-[disjoint_paths] problem is tractable, cf [kawarabayashi2022directed] -[kawarabayashi2022directed] shows that a [graph_directed] with high directed treewdith contains a [directed_grid] as [butterfly_minor] +[kawarabayashi2022directed] shows that a [directed_graph] with high directed treewidth contains a [directed_grid] as [butterfly_minor] - polynomial bounds known [hatzel2019polynomial] Up: [treewidth], [width_measure_directed] -See also: [pathwidth_directed], [grid_minor_directed] +See also: [directed_pathwidth], [grid_minor_directed] + +Aliases: Directed treewidth diff --git a/triangle_inequality_strong b/triangle_inequality_strong @@ -3,3 +3,5 @@ forall xyz, d(x,y) <= max(d(x,z), d(z,y)) Up: [triangle_inequality] + +Aliases: strong triangle equality diff --git a/ucrpq_strongly_minimal b/ucrpq_strongly_minimal @@ -1,4 +1,4 @@ -# CRPQ strongly minimal +# Strongly minimal UCRPQ A [UCRPQ] Q is *strongly minimal* if it has a [homomorphism_minimal] [UCRPQ_expansion] whose [core] has a number of [CRPQ_segments] equal to the number of [atoms] of Q @@ -8,4 +8,4 @@ By Corollary IV.2.16 of [morvan2025homomorphism], it is [EXPSPACE_hard] to test Up: [crpq_minimization] -Aliases: strongly minimal CRPQ, strongly minimal UCRPQ +Aliases: strongly minimal CRPQ, strongly minimal UCRPQ, CRPQ strongly minimal diff --git a/ultrametric b/ultrametric @@ -1,7 +1,9 @@ # Ultrametric -[metric] satisfying [triangle_inequality_strong] +An *ultrametric* is a [metric] that satisfies the [strong_triangle_inequality] Up: [distance] See also: [metric_space] + +Aliases: ultrametrics diff --git a/unambiguous_marked_product b/unambiguous_marked_product @@ -1,9 +0,0 @@ -# Unambiguous_marked_product - -A [marked_product] which is [unambiguity] in the sense that there is a unique decomposition - -[unambiguous_language] formed of these - -Up: [marked_product], [unambiguity] - -Aliases: unambiguous marked products diff --git a/update b/update @@ -19,3 +19,5 @@ Kinds of updates supported for [dynamic_data]: See also: [batch_updates] Up: [dynamic_data] + +Aliases: updates diff --git a/vardi1989note b/vardi1989note @@ -1,4 +1,4 @@ -# Vardi1989note +# vardi1989note By [moshe_vardi] diff --git a/wang2021query b/wang2021query @@ -1,4 +1,4 @@ -# Wang2021query +# wang2021query "Query evaluation by circuits" diff --git a/wang2024sampling b/wang2024sampling @@ -1,4 +1,4 @@ -# Wang2024sampling +# wang2024sampling uses [degree_constraints] diff --git a/zhao2024evaluating b/zhao2024evaluating @@ -1,4 +1,4 @@ -# Zhao2024evaluating +# zhao2024evaluating [computational_complexity] of [datalog_semiring_query_evaluation] under [naturally_ordered_semiring]