commit a692ba6dc77b6c5c20e6461f570e6dd9ca60c417 parent 068e347fa40af89b51a92c3e97505efc76552992 Author: Antoine Amarilli <a3nm@a3nm.net> Date: Sun, 22 Jun 2025 14:05:24 +0200 commit with codex Diffstat:
70 files changed, 553 insertions(+), 18 deletions(-)
diff --git a/abboud2020fine b/abboud2020fine @@ -0,0 +1,5 @@ +# abboud2020fine + +does not seem to talk about [Boolean_matrix_multiplication], only about [min_plus_matrix_multiplication] + +Up: [parity_fine_grained] diff --git a/acyclicity b/acyclicity @@ -0,0 +1,11 @@ +# Acyclicity + +- [graph_acyclicity] +- [hypergraph_acyclicity] +- [query_acyclic] + - [CQ_acyclic] + - [acyclic_SJFCQ] + - [acyclic_free_connex] +- [datalog_acyclic] + +Up: [mathematics] diff --git a/all_pairs_shortest_path b/all_pairs_shortest_path @@ -29,4 +29,4 @@ Up: [shortest_path], [fine_grained_complexity_problems] See also: [reachability_all_pairs] -Aliases: APSP +Aliases: APSP, all pair shortest path diff --git a/benameur2024complexity b/benameur2024complexity @@ -0,0 +1,13 @@ +# Benameur2024complexity + +about [hunters_and_rabbit_directed] + +shows that recognizing graphs where the rabbit wins is [np_hard] even against just one hunter +- and [pspace] upper bound +- [open_question] of whether it is [pspace_hard] + +connections to [matrix_mortality] + +Up: [academic_paper] on [hunters_and_rabbit_directed] + +See also: [benameur2024cops] diff --git a/boolean_crpq b/boolean_crpq @@ -0,0 +1,7 @@ +# Boolean CRPQ + +A [CRPQ] with no output [variables] + +Up: [Boolean_query], [crpq] + +Aliases: Boolean CRPQs diff --git a/catalytic_space b/catalytic_space @@ -0,0 +1,11 @@ +# Catalytic space + +A [computational_model] where you can use memory that must be restored to its initial state at the end + +Introduced in [buhrman2014computing] + +Cf https://www.quantamagazine.org/catalytic-computing-taps-the-full-power-of-a-full-hard-drive-20250218/ + +Can be achieved by [transparent_computation], which is a special case of [reversible_computing] + +Up: [complexity_space] diff --git a/chen2023random b/chen2023random @@ -0,0 +1,5 @@ +# chen2023random + +https://arxiv.org/abs/2302.13549 + +Up: [academic_paper] about [enumeration_random_order] diff --git a/chung1992universal b/chung1992universal @@ -0,0 +1,5 @@ +# chung1992universal + +uses [eulerian_cycle] + +Up: [academic_paper] about [universal_word] diff --git a/clique b/clique @@ -16,6 +16,6 @@ clique on [hypergraph]: [hyperclique] Up: [graph] -See also: [cliquewidth], [fine_grained_complexity], [treewidth], [graph_minor], [graph_complete], [hyperclique] +See also: [cliquewidth], [fine_grained_complexity], [treewidth], [graph_minor], [graph_complete], [hyperclique], [multicolored_clique] Aliases: cliques diff --git a/computing b/computing @@ -0,0 +1,12 @@ +# Computing + +https://en.wikipedia.org/wiki/Unconventional_computing + +- [distributed_computing] +- [reversible_computing] +- [quantum_computing] +- [dionaea_muscipula_computer] + +See also: [computer], [computability] + +Up: [computer_science] diff --git a/conjecture b/conjecture @@ -3,12 +3,15 @@ [mathematics_meta] about conjectures : - https://igorpak.wordpress.com/2020/12/10/what-if-they-are-all-wrong/ +- [bunkbed_conjecture] - [Cerny_conjecture] - [Cramer's_conjecture] -- [exact_triangle_conjecture] +- [Collatz_conjecture] +- [Exact_triangle_conjecture] - [Goldbach_conjecture] - [Hadwiger_conjecture] - [Lovasz_conjecture] +- [Lovász_Woodall_conjecture] - [OV_conjecture] - [K_OV_conjecture] - [OMv_conjecture] @@ -19,8 +22,6 @@ - [Tuzas_conjecture] - [unfair_01_polynomial_conjecture] - [unique_games_conjecture] -- [bunkbed_conjecture] -- [Lovász_Woodall_conjecture] Up: [mathematics_meta] diff --git a/conjunctive_query_acyclic b/conjunctive_query_acyclic @@ -23,6 +23,6 @@ Special case: See also: [fagin1983degrees], [guarded_fragment], [alpha_acyclic], [conjunctive_query_cyclic] -Up: [conjunctive_query] +Up: [conjunctive_query], [query_acyclic] Aliases: acyclic conjunctive query, acyclic conjunctive queries, acyclic CQ, acyclic CQs, CQ acyclic, acyclic queries, acyclic query diff --git a/conjunctive_query_boolean b/conjunctive_query_boolean @@ -5,3 +5,5 @@ Up: [conjunctive_query], [query_boolean] Aliases: Boolean CQ, Boolean CQs, Boolean conjunctive query, BCQ, BCQs, Boolean conjunctive queries + +See also: [boolean_UCQ] diff --git a/constant_delay b/constant_delay @@ -0,0 +1,7 @@ +# Constant delay + +An [enumeration_algorithm] is *constant delay* if its [enumeration_delay] is bounded by a [constant] + +Up: [enumeration_delay] + +See also: [linear_preprocessing_constant_delay] diff --git a/counting_mso b/counting_mso @@ -0,0 +1,10 @@ +# Counting MSO + +[monadic_second_order_logic] where you want to compute the total weight of assignments in a [semiring] +- all elements have a value +- all assignments have a value obtained by summing the value of the variables +- we want to compute some aggregation of the weights of all assignments + +See also: [weighted_mso] + +Up: [monadic_second_order_logic], [counting_weighted_mso] diff --git a/counting_problem b/counting_problem @@ -16,3 +16,5 @@ - [sharp_dfa] Up: [computational_problem], [counting] + +Aliases: counting problems diff --git a/crpq b/crpq @@ -3,6 +3,7 @@ [Special_cases]: - [RPQ] - [CQ] +- [Boolean_CRPQ] [Generalizations]: - [C2RPQ] diff --git a/crpq_containment b/crpq_containment @@ -2,7 +2,15 @@ [EXPSPACE_complete]: cf [calvanese2000containment] -[beaudou2023complexity] +[morvan2025homomorphism] Proposition IV.5.1: [EXPSPACE_hardness] already holds: +- on a fixed [alphabet] +- for [Boolean_CRPQs] +- the [formal_languages] are not empty and do not contain the [empty_word] +- the [LHS] is just a single atom +- the [RHS] is just a set of parallel atoms +Reduction in [figueira2020containment] from a [tiling_problem] + +Different kind of [homomorphism] studied in [beaudou2023complexity], with an [EXPTIME] upper bound Up: [crpq], [query_containment] diff --git a/crpq_minimization b/crpq_minimization @@ -4,11 +4,15 @@ The [computational_problem] of computing from a [CRPQ] Q a [CRPQ_minimal] which Covered in [morvan2025homomorphism] -Formal [decision_problem] for [UCRPQs]: [UCRPQ_minimization_problem] +Formal [decision_problem] for [CRPQs]: [CRPQ_minimization_problem] Notions: - [CRPQ_fully_contracted] - [CRPQ_non_redundant] - [CRPQ_strongly_minimal] +Sometimes admits [reductions] from [CRPQ_containment], cf [morvan2025homomorphism] Section IV.5.2 + Up: [crpq], [query_minimization] + +See also: [ucrpq_minimization] diff --git a/crpq_minimization_problem b/crpq_minimization_problem @@ -0,0 +1,13 @@ +# CRPQ minimization problem + +[Decision_problem] defined in [morvan2025homomorphism], p91: +- Input: a [CRPQ] Q and integer k +- Output: is there a [query_equivalent] [CRPQ] with at most k [atoms] which is equivalent to Q + +The problem is [EXPSPACE_hard] ([morvan2025homomorphism], Theorem IV.5.2) and in [2EXPSPACE] ([CRPQ_minimization_upper_bound], [morvan2025homomorphism], Theorem IV.3.1) + +In fact, by [morvan2025homomorphism] Theorem IV.5.2, it is already [EXPSPACE_hard] to determine if a [Boolean_CRPQ] with 4 variables is equivalent to a [Boolean_CRPQ] with a single atom + +See also: [ucrpq_minimization_problem] + +Up: [computational_problem], [CRPQ_minimization] diff --git a/crpq_non_redundant b/crpq_non_redundant @@ -0,0 +1,7 @@ +# Non-redundant CRPQ + +A [CRPQ] is *non-redundant* if it does not contain any [CRPQ_redundant_atom] + +By Proposition IV.2.3 of [morvan2025homomorphism], it is [EXPSPACE_complete] to test if a [CRPQ] or [UCRPQ] is non-redundant + +Up: [crpq_minimization] diff --git a/crpq_query_equivalence b/crpq_query_equivalence @@ -0,0 +1,7 @@ +# CRPQ query equivalence + +The [query_equivalence_problem] for [CRPQs] + +It is [EXPSPACE_complete]: [florescu1998query] + +Up: [query_equivalence], [CRPQs] diff --git a/cyk b/cyk @@ -0,0 +1,5 @@ +# CYK + +[Algorithm] for [parsing] of [context_free_grammars] running in [cubic] time + +Up: [Algorithm] for [CFG_parsing] diff --git a/database_theory_techniques b/database_theory_techniques @@ -2,5 +2,8 @@ - [shredding], going from high arity to [arity_two] - [ucq_to_cq] +- [tagging_trick] Up: [database_theory] + +Aliases: database theory technique diff --git a/enumeration_extensions b/enumeration_extensions @@ -0,0 +1,20 @@ +# Enumeration extensions + +Extensions of [enumeration] problems: + +- [Ordered_enumeration]: enumerate in a specific [order] +- [Direct_access]: access the i-th solution by number +- [Ranked_access]: access the i-th solution in a given order +- [Counting]: count the number of solutions + - [counting_cqs] + - [counting_mso] +- [Tuple_testing]: test if given solution is actually a solution +- [Direct_access_reverse]: given a solution, return its index +- [Uniform_sampling] + +## Other extensions + +- [incremental_maintenance_enumeration] + - [change_propagation] + +Up: [enumeration] diff --git a/enumeration_random_order b/enumeration_random_order @@ -0,0 +1,7 @@ +# Enumeration in random order + +- [chen2023random] + +See also: [uniform_sampling] + +Up: [enumeration] diff --git a/graph_homomorphism b/graph_homomorphism @@ -0,0 +1,11 @@ +# Graph homomorphism + +A [homomorphism] from a [graph] to an [other] + +[Computational_problem]: [graph_homomorphism_problem] + +- generalization in [kawarabayashi2020minimum] called [minimum_violation_problem]: "how many edges to remove to have a homomorphism?" + +Up: [homomorphism] of [graph] + +See also: [graph_isomorphism], [CSP] diff --git a/graph_learning b/graph_learning @@ -0,0 +1,5 @@ +# Graph learning + +- [hypergraph_learning] + +See also: [interactive_boolean_evaluation] diff --git a/graph_oriented b/graph_oriented @@ -0,0 +1,10 @@ +# Graph oriented + +A [directed_graph] with no [self_loops], which is a [simple_graph], and whose undirected underlying graph is also a simple graph +- no edges (u,v) and (v,u) + +[conjecture]: [second_neighborhood_problem] + +Up: [graph_directed] + +Aliases: oriented graph diff --git a/graph_problem b/graph_problem @@ -0,0 +1,28 @@ +# Graph problem + +- [graph_coloring] +- [network_flow] +- [reconfiguration_problem] +- [graph_homomorphism_problem] + - [minimum_violation_problem] +- [shortest_path] + - [all_pair_shortest_path] +- [spanning_tree] +- [minimum_cut] + - [maximum_cut] +- [maximum_matching] + - [perfect_matching] +- [densest_subgraph] +- [graph_orientation] +- existence of [nowhere_zero_flows] +- [graph_layout] +- [graph_isomorphism_problem] +- [vantage_point_selection_problem] +- [domino_problem] +- [graph_reconstruction] +- [clique_problem] +- [cycle_problem] + +Up: [computational_problem] on [graph] + +See also: [constraint_satisfaction_problem] diff --git a/hailstone_sequence b/hailstone_sequence @@ -0,0 +1,5 @@ +# Hailstone sequence + +Occurs in [Collatz_conjecture] + +Up: [sequence] diff --git a/han2008generalizations b/han2008generalizations @@ -0,0 +1,5 @@ +# Han2008generalizations + +contains [paper_bug] because depends on wrong statement, according to [caron2017hierarchy] + +Up: [academic_paper], [regular_expression_deterministic] diff --git a/heap_automata b/heap_automata @@ -0,0 +1,8 @@ +# Heap automata + +apparently only studied in [computer_science_stack_exchange]: +- https://cs.stackexchange.com/questions/110/determining-capabilities-of-a-min-heap-or-other-exotic-state-machines + +See also: [pushdown_automaton] + +Up: [automata], [heap] diff --git a/hu2023finding b/hu2023finding @@ -0,0 +1,20 @@ +# Hu2023finding + +[academic_paper] on [minimal_witness] + +## Results + +Only on [conjunctive_query_self_join_free] + +- if Q has [head_cluster_property] then [ptime], otherwise [np_complete] +- if Q has [head_domination_property] then constant-factor [approximation], otherwise conditionally no such algorithm +- general [approximation] algorithm; some algorithms for specific query classes + +Relationship to: [directed_steiner_forest] problem + +Future work: +- [approximation]: picture is not complete +- [self_joins] +- the variant of [minimal_witness] where you want to witness only a fraction of the query results + +Up: [academic_paper] on [minimal_witness] diff --git a/irrelevant_vertex_technique b/irrelevant_vertex_technique @@ -0,0 +1,11 @@ +# Irrelevant vertex technique + +A [technique] in [graph_theory] + +See [adler2017irrelevant] + +Used in [liu2025disjoint] + +Up: [graph] + +See also: [grid_minor], [treewidth], [alexandre_vigny] diff --git a/locality_formal_languages b/locality_formal_languages @@ -0,0 +1,7 @@ +# Locality formal languages + +For instance in [amarilli2023locality] + +Tool: [Straubing's_delay_theorem] + +Up: [locality], [formal_languages] diff --git a/logspace_reduction b/logspace_reduction @@ -5,3 +5,5 @@ Can be used to show that problems are [nl_complete] Up: [reduction] + +Aliases: logspace reductions diff --git a/many_one_reduction b/many_one_reduction @@ -9,3 +9,5 @@ Called "Karp reduction" when it is [ptime_reduction] Up: [reduction] See also: [turing_reduction], [weihrauch_reduction] + +Aliases: Many one reductions, Karp reduction, Karp reductions diff --git a/maximum_matching_approximation b/maximum_matching_approximation @@ -0,0 +1,5 @@ +# Maximum matching approximation + +The [approximation_problem] of maintaining an (1+epsilon)-approximation of a [maximum_matching] + +Up: [approximation_problem] of [maximum_matching] diff --git a/median_of_medians b/median_of_medians @@ -0,0 +1,11 @@ +# Median of medians + +https://en.wikipedia.org/wiki/Median_of_medians + +Find an approximate [median] in an unsorted [array] in [linear_time] + +Can be used to make [quickselect] run in [linear_time] + +See also: [selection_algorithm] + +Up: [algorithms_list] diff --git a/nothing_up_my_sleeve_number b/nothing_up_my_sleeve_number @@ -0,0 +1,7 @@ +# Nothing up my sleeve number + +https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number#Limitations + +See also: [kolmogorov_complexity], [nonce] + +Up: [cryptography] diff --git a/np_complete b/np_complete @@ -21,9 +21,11 @@ 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_reduction] and [ptime_reduction] are different, cf https://en.wikipedia.org/wiki/Log-space_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] -Up: [complete] for [nptime] +Up: [completeness] for [nptime] See also: [intractability], [np_hard], [conp_complete] diff --git a/parity b/parity @@ -3,6 +3,7 @@ - [parity_games] / [parity_acceptance] - [parity_p] - [parity_fine_grained] +- [sat_parity] - [even] - [odd] diff --git a/parity_fine_grained b/parity_fine_grained @@ -0,0 +1,9 @@ +# Parity fine grained + +[Computational_problems] extended with parity constraints + +- [abboud2020fine]: Fine-Grained Complexity of Parity Problems + +Up: [parity], [fine_grained_complexity] + +See also: [modulo_graph] diff --git a/parity_p b/parity_p @@ -4,6 +4,8 @@ https://en.wikipedia.org/wiki/Parity_P [Computational_problem] solvable by [nondeterministic_Turing_machine] where the [acceptance_condition] is that the number of [accepting_runs] is [even]. +- [parity_p_complete] + Up: [parity], [complexity_class] See also: [parity_fine_grained], [Z_2Z] diff --git a/parsing b/parsing @@ -0,0 +1,5 @@ +# Parsing + +- [CFG_parsing] + +Up: [computational_problem] diff --git a/pattern_language_computational_problems b/pattern_language_computational_problems @@ -0,0 +1,7 @@ +# Pattern language computational problems + +- [pattern_language_equivalence]: [open_problem] if it is [decidable] +- [pattern_language_membership] +- [pattern_language_inclusion] + +Up: [pattern_language] diff --git a/pattern_language_membership b/pattern_language_membership @@ -0,0 +1,7 @@ +# Pattern language membership + +[membership_problem] for [pattern_languages]: given a [pattern_with_variables] p and [word] w, decide if w can be obtained from p via a substitution + +- [nowotka2024equivalence], [NP_complete] for both erasing and nonerasing substitutions + +Up: [pattern_language_computational_problems] diff --git a/polynomial_multilinear b/polynomial_multilinear @@ -0,0 +1,9 @@ +# Polynomial multilinear + +A [polynomial] where, in the [polynomial_expanded], for every [monomial], the [exponent] of every [variable] is at most 1 + +For polynomials with just one [variable], you get an [affine_function] + +Up: [polynomial] + +See also: [trio] diff --git a/query_boolean b/query_boolean @@ -6,6 +6,11 @@ For [queries] with [free_variables] that are [first_order], the [computational_c In [logic], this is called a [sentence] +[Query_classes]: +- [Boolean_CQ] +- [Boolean_UCQ] +- [Boolean_CRPQ] + Up: [query] Aliases: boolean query diff --git a/query_containment_problem b/query_containment_problem @@ -2,10 +2,11 @@ [Computational_problem] of deciding [query_containment] -The query containment problem and [query_equivalence_problem] are [NP_complete] for [CQs] and [UCQs] +- [CQ_containment_problem] for [CQs]: [NP_complete] +- [UCQ_containment_problem] for [UCQs]: [NP_complete] Up: [query_containment] Aliases: QCP -See also: [bag_query_containment] +See also: [bag_query_containment], [query_equivalence_problem] diff --git a/query_equivalence_problem b/query_equivalence_problem @@ -0,0 +1,13 @@ +# Query equivalence problem + +The [decision_problem], given two [queries], of deciding whether they are [query_equivalent] + +Always admits a [reduction] to the [query_containment_problem], because [query_equivalence] can be decided by checking [double_inclusion] + +- [CQ_equivalence_problem] for [CQs]: [NP_complete] +- [UCQ_equivalence_problem] for [UCQs]: [NP_complete] +- [CRPQ_equivalence_problem] + +Up: [decision_problem], [query_equivalence] + +See also: [query_containment_problem], [bag_query_equivalence_problem] diff --git a/random_permutation b/random_permutation @@ -0,0 +1,5 @@ +# Random permutation + +[terence_tao]: https://terrytao.wordpress.com/2011/11/23/the-number-of-cycles-in-a-random-permutation/ + +Up: [random_structure], [permutation] diff --git a/range_sum b/range_sum @@ -0,0 +1,8 @@ +# Range sum + +The *range sum* problem is that of maintaining a collection of points and answer queries asking about the sum of all points in a range +- can be posed in multiple [dimensions] + +[lu2022range]: range sum, multidimensional points, [monoid] weights + +Up: [range_query] with [sum], [Dynamic_data] diff --git a/reduct b/reduct @@ -0,0 +1,7 @@ +# Reduct + +Given a [database_instance] I on a [relational_signature] σ, for a [subsignature] σ' of σ, the *reduct* of I on σ' is the [subdatabase] J of I obtained by keeping precisely the [facts] of I on the [relations] of σ' + +Up: [subdatabase] + +See also: [expansion] diff --git a/reduction_3dm_subset_sum b/reduction_3dm_subset_sum @@ -0,0 +1,11 @@ +# Reduction 3dm subset sum + +reduction from [3_dimensional_matching] to [subset_sum]: +- for n = |X| + |Y| + |Z| +- take a base K which is sufficiently big to avoid [carry] +- reach (1...1) n times +- every triple gives you a number with exactly 3 bits carrying a 1 corresponding to its elements + +Shows that [subset_sum] is [NP_hard] + +Up: [reduction], [subset_sum] diff --git a/regular_language_union_free b/regular_language_union_free @@ -0,0 +1,13 @@ +# Regular language union free + +The [regular_languages] whose definition as a [regular_expression] does not use the [union_operator] + +- [nagy2006union] + - they are accepted by [1_cycle_free_path_automata] +- [jiraskova2011complexity] + +Up: [regular_language_family] + +See also: [union] + +Aliases: union free regular language, union free regular languages diff --git a/sat_parity b/sat_parity @@ -0,0 +1,11 @@ +# Sat parity + +The variant of [Boolean_satisfiability] where we ask whether the number of [satisfying_assignments] is [even] or [odd] + +This is [Parity_P_complete], cf [valiant2006accidental] + +Up: [parity], [Boolean_satisfiability] + +See also: [maj_SAT], [gt_maj_sat] + +Aliases: parity SAT diff --git a/shapley_value b/shapley_value @@ -0,0 +1,16 @@ +# Shapley value + +[survey_papers]: +- [bertossi2024shapley] +- [luo2024applications] + +Results: + +- [karmakar2024expected] on [shapley_value_expected] +- connections with [model_counting] and [pqe] + - [bienvenu2023when] + - [kara2023from] + +- [shapley_value_omqa] + +See also: [pqe], [explainability], [shap_score], [stable_marriage] diff --git a/shortest_distinguishing_subsequence b/shortest_distinguishing_subsequence @@ -0,0 +1,7 @@ +# Shortest distinguishing subsequence + +The [computational_problem], given a set S of strings, of finding a shortest [distinguishing_subsequence] + +can be solved in [PTIME], cf [crochemore2003directed] Section 4.5 + +Up: [computational_problem], [distinguishing_subsequence] diff --git a/simple_graph b/simple_graph @@ -0,0 +1,7 @@ +# Simple graph + +A [graph] which is not a [multigraph], i.e., there cannot be multiple copies of the same [edge] + +Up: [graph] + +See also: [set_semantics] diff --git a/simple_regular_expressions b/simple_regular_expressions @@ -1,8 +1,22 @@ # Simple regular expressions -defined in [figueira2024boundedness] +- version defined in [figueira2024boundedness] + - allows w^* for a [word] w + - allows [regular_expressions] without [Kleene_star] + - allows [regular_expression_repetition] -allows w^* for a [word] w, or a [regular_expression] without [Kleene_star] -- allows [regular_expression_repetition] +- version defined in [morvan2025homomorphism] + - allows a^* for a letter a + - allows a_1 + ... + a_m for letters a_1, ..., a_m + +- versions also defined in [figueira2020containmentb] "Containment of Simple +Conjunctive Regular Path Queries" + - considers various subsets of features of atom types: + - a + - a^* + - A + - A^* + - hard feature is [disjunction] under [kleene_star], causes [query_containment] to go from [NP_complete] to [EXPSPACE_complete] + - otherwise [query_containment] drops to [Pi_p_2] or [PSPACE] Up: [regular_expression] diff --git a/stable_marriage b/stable_marriage @@ -0,0 +1,7 @@ +# Stable marriage + +- [gale_shapley_algorithm] + +See also: [shapley_value] + +Up: [TCS] diff --git a/tagging_trick b/tagging_trick @@ -0,0 +1,6 @@ +# Tagging trick + +The [database_theory_technique] of tagging the domain of a database with the variable to which each element should be mapped +- useful for [queries] with [self_joins] + +Up: [projection], [database_theory_techniques] diff --git a/tuple_generating_dependency b/tuple_generating_dependency @@ -0,0 +1,29 @@ +# TGD + +Also called "existential rules" + +- [zhang2021characterizing]: [expressiveness] of [OMQA] in various formalisms +- [carral2022normalizations] on normalization of rules + +- [feller2022finite] + +## Types + +- [inclusion_dependency] +- [tuple_generating_dependency_full]: no [existential_quantifier] in head + - related to [datalog] +- [tuple_generating_dependency_guarded], in the [guarded_fragment] +- [tuple_generating_dependency_frontier_guarded] +- [tuple_generating_dependency_clique_guarded] +- [tuple_generating_dependency_linear] +- [tuple_generating_dependency_single_head] +- [tuple_generating_dependency_sticky] +- [tuple_generating_dependency_acyclic] +- [tuple_generating_dependency_weakly_acyclic] +- [word_constraint] + +Up: [database_dependency] + +See also: [datalogpm], [denial_constraint] + +Aliases: TGD, TGDs diff --git a/tuple_testing b/tuple_testing @@ -0,0 +1,11 @@ +# Tuple testing + +Testing if an input tuple is a solution to a [query] + +- [tuple_testing_automaton] +- [rpq_answer_testing] +- [incremental_maintenance_tuple_testing] + +See also: [dynamic_data], [enumeration], [enumeration_extensions] + +Up: [database_theory] diff --git a/turing_machine_symmetric b/turing_machine_symmetric @@ -0,0 +1,9 @@ +# Turing_machine_symmetric + +A [Turing_machine] where all transitions can be taken in reverse + +[Turing_machine_symmetric_automata] + +Up: [turing_machine] + +See also: [automata_symmetric] diff --git a/turing_reduction b/turing_reduction @@ -1,11 +1,14 @@ # Turing reduction -[reduction] which uses target problem as [oracle] +A [reduction] which uses target problem as [oracle] - "Cook reduction" : Turing reduction which is [ptime_reduction] -Not always very different from [many_one_reduction] for [counting_problem], cf argument https://dbt.zulipchat.com/#narrow/stream/417238-Dagstuhl-24032/topic/Open.20problems/near/425331364 +Not always very different from [many_one_reductions] for [counting_problems] +- cf argument https://dbt.zulipchat.com/#narrow/stream/417238-Dagstuhl-24032/topic/Open.20problems/near/425331364 Up: [reduction] See also: [alan_turing], [many_one_reduction] + +Aliases: Turing reductions, Cook reduction, Cook reductions diff --git a/ucrpq_minimization b/ucrpq_minimization @@ -0,0 +1,7 @@ +# Ucrpq minimization + +[Computational_problem]: [UCRPQ_minimization_problem] + +Up: [UCRPQ], [query_minimization] + +See also: [crpq_minimization] diff --git a/ucrpq_minimization_problem b/ucrpq_minimization_problem @@ -12,4 +12,4 @@ Different from [CRPQ_minimization] in the sense that there are [minimal_CRPQs] t Up: [crpq_minimization], [decision_problem] -Aliases: CRPQ minimization problem +See also: [CRPQ_minimization_problem]