commit 649fbe64bb10f53eb256950fe258f6c4161f4638 parent e549435f14ec029fe0f04711500d3baea2ccfd04 Author: Antoine Amarilli <a3nm@a3nm.net> Date: Tue, 4 Mar 2025 12:08:05 +0100 Merge branch 'master' of a3nm.net:git/wiki_research Diffstat:
212 files changed, 1359 insertions(+), 138 deletions(-)
diff --git a/absent_factor b/absent_factor @@ -0,0 +1,9 @@ +# Absent factor + +A [word] u is an *absent factor* of a [word] v if u does not occur as a [factor] of v + +Mentioned in [kosche2021absent] / [kosche2023absent] + +Up: [factor] + +See also: [absent_subsequence] diff --git a/absent_subsequence b/absent_subsequence @@ -0,0 +1,12 @@ +# Absent subsequence + +A [word] u is an *absent subsequence* of a [word] v if u does not occur as a [subsequence] of v + +Defined in [kosche2021absent] / [kosche2023absent], along with: + +- [minimal_absent_subsequence]: an absent subsequence where every strict [subsequence] is not absent +- [shortest_absent_subsequence]: an absent subsequence whose [length] is [minimal] + +Up: [subsequence] + +See also: [absent_factor] diff --git a/ac0 b/ac0 @@ -1,9 +0,0 @@ -# Ac0 - -[ac] circuit with constant [depth] (and unbounded [fan_in], and polynomial size) - -AC0 = [first_order_logic] + arbitrary numerical predicates arbitrary arity - -Up: [ac] - -See also: [acc0] diff --git a/accepting_run b/accepting_run @@ -0,0 +1,9 @@ +# Accepting run + +A [run] which finishes on a [final_state] + +Up: [run] + +Aliases: accepting runs + +See also: [rejecting_run] diff --git a/algebra b/algebra @@ -5,5 +5,6 @@ - [matrix] - ... - [vector_space] +- [algebra_basic_definitions] Up: [mathematics] diff --git a/all_pairs_shortest_path b/all_pairs_shortest_path @@ -23,8 +23,10 @@ connection between APSP and [distance_product] ([matrix_multiplication] in [semi Approximation: [all_pairs_shortest_path_approximate] -Beware: APSP can also mean "All pairs suffix prefix", cf [gusfield1992efficient], [zuba2024approximate] +Beware: APSP can also mean [All_pairs_suffix_prefix] Up: [shortest_path], [fine_grained_complexity_problems] See also: [reachability_all_pairs] + +Aliases: APSP diff --git a/alphabet_unary b/alphabet_unary @@ -0,0 +1,10 @@ +# Alphabet unary + +[Alphabet] which is a [singleton], i.e., contains one single [letter] + +- [language_unary] +- [automata_unary] + +Up: [alphabet] + +Aliases: unary alphabet, unary alphabets diff --git a/approximation b/approximation @@ -12,8 +12,8 @@ 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] -- [sharp_is]: no FPRAS to count the [independent_set] of a [graph] +- 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] +- [sharp_is]: no [FPRAS] to count the [independent_sets] of a [graph] - no [FPRAS] for [monotone2cnf] ([calautti2022query]), cf [sharp_satisfiability_fpras] - [hardness_of_approximation] @@ -33,4 +33,4 @@ Other notions: Up: [research_directions] -Aliases: approximate counting +Aliases: approximate counting, approximated diff --git a/apsp_hypothesis b/apsp_hypothesis @@ -5,7 +5,7 @@ - equivalent to [negative_triangle] - you can use [all_pairs_shortest_path] to compute [negative_triangle] - other direction more involved -- equivalent to [mpp_minimum] (find if the minimum diagonal entry of the min-plus product of three matrices A B C is <0) +- equivalent to [mpp_minimum] The equivalences to [all_pairs_shortest_path] and [mpp_minimum] are from [williams2018subcubic] diff --git a/arboricity b/arboricity @@ -1,5 +1,10 @@ # Arboricity +A [width_measure] on [undirected_graphs]: the minimum number of [spanning_forests] needed to cover all [edges] of the [graph] +- equivalently, the [minimum] number of [forests] in which the [edges] can be partitioned + +A [planar_graph] has arboricity has arboricity at most 3 + Connection between [arboricity] and [dynamic_data] in [lu2021towards] - [chiba1985arboricity] @@ -8,6 +13,8 @@ Connection between [arboricity] and [dynamic_data] in [lu2021towards] - https://github.com/maxdan94/kmotif - [ortmann2014triangle] algorithm for [triangle_listing] -[bressan2022complexity]: optimality of the results of chiba for [graph_pattern_counting] +[bressan2022complexity]: optimality of the results of [chiba1985arboricity] for [graph_pattern_counting] Up: [width_measure] + +See also: [degeneracy], [thickness], [pseudoarboricity] diff --git a/automata_alternating b/automata_alternating @@ -0,0 +1,11 @@ +# Automata alternating + +An [automaton] where the [states] can be [existential_states] or [universal_states] + +Generalizes [NFAs] + +Can be seen as an [arena] in [game_theory] + +Up: [automata_types] + +Aliases: alternating automaton, alternating automata diff --git a/automata_complementation b/automata_complementation @@ -5,3 +5,5 @@ - hard also for [word_automaton_unambiguous] Up: [complementation], [automata] + +Aliases: automaton complement, automaton complementation diff --git a/automata_concepts b/automata_concepts @@ -3,6 +3,7 @@ - [state] - [initial_state] - [final_state] + - [nonfinal_state] - [sink_state] - [transient_state] - [transition] diff --git a/automata_evaluation b/automata_evaluation @@ -0,0 +1,12 @@ +# Automata evaluation + +Given an [automaton] A and a [word] w, determine if A accepts w + +- for [DFAs]: can be done in O(|w|), simply by following [transitions] +- for [NFAs]: can be done in O(|w| |A|) by [state_set_simulation] + - [conditional_lower_bound] in [backurs2016which] + - reduction from [OV_conjecture] + +- [automata_evaluation_practice] + +Up: [automata_problems] diff --git a/automata_weighted b/automata_weighted @@ -1,14 +1,22 @@ # Automata weighted -[automata] with [weight]s on [transition]s and on [final_state]s +[automata] with [weights] on [transitions] and on [final_states] and on [initial_states] -associates each [word] to an [integer] +associates each [word] to an [integer], or to a value in a [semiring] + +- [initial_weight] +- [final_weight] +- weight for every [transition] given a [word]: - [sum] over possible [run]s -- [product] over [transition]s and [final_state]s used +- [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] + +Schützenberger, 1961 -can be done in [semiring] +- [automata_weighted_conjugacy] Up: [automata] diff --git a/automaton_epsilon_transitions b/automaton_epsilon_transitions @@ -3,3 +3,5 @@ [automata_nondeterministic] with [epsilon_transition] Up: [automata_types] + +Aliases: NFA epsilon diff --git a/automaton_equivalence b/automaton_equivalence @@ -1,8 +1,9 @@ # Automaton equivalence -[pspace_complete] on [automata_nondeterministic] - -[ptime] on [automata_deterministic] via [product_construction] +- [pspace_complete] on [automata_nondeterministic] +- [ptime] on [automata_deterministic] via [product_construction] +- [automaton_equivalence_pushdown_automaton] +- [automaton_equivalence_pushdown_automaton_deterministic] Up: [automata_problems] 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/bag_cq_containment b/bag_cq_containment @@ -0,0 +1,9 @@ +# Bag cq containment + +bag [query_containment] for [CQs] is [open_problem] + +- introduced in [chaudhuri1993optimization] +- withdrawn claim of [Pi_2_p]-hardness +- only known [lower_bound] is [NP_hard] + +Up: [containment_bag_semantics], [CQs] diff --git a/bellman_ford_algorithm b/bellman_ford_algorithm @@ -6,3 +6,5 @@ Up: [shortest_path_algorithm] Aliases: Bellman-Ford, Bellman Ford + +See also: [single_source_shortest_path_faster] diff --git a/boolean_formula b/boolean_formula @@ -8,6 +8,7 @@ An [expression] which represents a [boolean_function], built from [literals] usi - [clause] - [term] - [literal] +- [Boolean_formulas_positive] Up: [representation] of [boolean_function] diff --git a/boolean_formulas_positive b/boolean_formulas_positive @@ -0,0 +1,7 @@ +# Boolean formulas positive + +A [Boolean_formula] which is [positive], i.e., does not use [negation] + +Up: [boolean_formula] + +Aliases: positive Boolean formula, positive Boolean formulas diff --git a/boolean_semiring b/boolean_semiring @@ -4,3 +4,5 @@ - it is a two-element [semiring] Up: [semiring] + +See also: [boolean] diff --git a/certain_answers b/certain_answers @@ -1,9 +1,11 @@ # Certain answers -Given a [query] Q and [uncertain_data] D, a *certain answer* is a [query_answer] which is true on every [possible_world] of D. If Q is a [Boolean_query], we talk about the query being certain +Given a [query] Q and [uncertain_data] D, a *certain answer* is a [query_answer] which is true on every [possible_world] of D. If Q is a [Boolean_query], we talk about the query being *certain* - [gheerbrant2023querying] Up: [uncertain_data] Aliases: certain answer + +See also: [possible_answers] diff --git a/chase b/chase @@ -1,9 +1,17 @@ # Chase -Process for [database_dependency] to construct [universal_model] +Given [database_dependencies] and an [instance], construct a (possibly infinite) [universal_model] - [chase_termination] - [gerlach2023general]: - - cf "weakly acyclic" and other sufficient conditions for chase termination + - cf [weakly_acyclic_TGDs] and other sufficient conditions for chase termination + +Variants: + +- [chase_restricted] +- [chase_oblivious] +- [chase_core] + +Can be used for [query_optimization] Up: [database_theory] diff --git a/chase_termination b/chase_termination @@ -0,0 +1,10 @@ +# Chase termination + +depends on the kind of [chase]: +- [chase_oblivious] +- [chase_restricted] + +recent work: [hanisch2024chase] + - idea: beyond [ptime] [data_complexity] + +Up: [chase], [termination] diff --git a/circuit b/circuit @@ -12,6 +12,7 @@ - [boolean_circuit] - [arithmetic_circuit] - [probabilistic_circuit] +- [Semiring_circuit] - [formula] ## Problems diff --git a/clique b/clique @@ -17,3 +17,5 @@ clique on [hypergraph]: [hyperclique] Up: [graph] See also: [cliquewidth], [fine_grained_complexity], [treewidth], [graph_minor], [graph_complete], [hyperclique] + +Aliases: cliques diff --git a/complementation b/complementation @@ -2,6 +2,7 @@ - [ddnnf_complementation] - [graph_complementation] +- [language_complementation] Up: [logic], [boolean_operator] diff --git a/complexity b/complexity @@ -8,3 +8,5 @@ Up: [theoretical_computer_science] See also: [complexity_as_a_service], [complexity_zoo] + +Aliases: complexity theory diff --git a/complexity_class b/complexity_class @@ -5,21 +5,8 @@ - [complexity_space] - [nlogspace] - [logspace] -- [complexity_time] - - [ptime] / [p_complete] - - [linear_time], [linear_time_nearly], [linear_time_almost] - - [np_intermediate], cf [ladners_theorem] - - [nptime] - - [conptime] - - [np_cap_conp] - - [exptime] - - [nexptime] - - [spanl] - - [pp] - - [pspace] - - [pspace_complete] - - [oplusp] oplusP - - [us] US +- [complexity_time]: [complexity_time_classes] +- [spanl] ## [complexity_hierarchy] diff --git a/complexity_measure b/complexity_measure @@ -0,0 +1,8 @@ +# Complexity measure + +- [complexity_time] +- [complexity_space] +- [incremental_time] +- [enumeration_delay] + +Up: [computational_complexity] diff --git a/complexity_space b/complexity_space @@ -1,6 +1,8 @@ # Complexity_space -- [savitchs_theorem]: we can simulate [nondeterministic] machine with quadratic blowup in space +- [savitchs_theorem]: we can simulate [nondeterministic] machine with [quadratic] blowup in space + +- [catalytic_space] Up: [complexity_measure] diff --git a/complexity_time b/complexity_time @@ -1,6 +1,8 @@ # Complexity time -The [asymptotic] running time of an [algorithm] +The [asymptotic] [running_time] of an [algorithm] + +- [complexity_time_classes] Up: [complexity_measure] diff --git a/compression_string b/compression_string @@ -6,3 +6,5 @@ - [substring_complexity] Up: [compression], [string] + +Aliases: compressed string, compressed strings diff --git a/computational_problem b/computational_problem @@ -36,6 +36,7 @@ - [word_problem] - [tiling_problem] - [domino_problem] +- [tree_evaluation_problem] Up: [theoretical_computer_science] diff --git a/computer_algebra b/computer_algebra @@ -2,5 +2,11 @@ - [grobner_basis], seems useful to solve [polynomial_equation] - matrixcalculus.org, calculs matriciels (différentiation etc) +- https://chadnauseam.com/coding/random/calculator-app on computer algebra for a calculator app: + - [bignum] + - [rationals] + - [algebraic_numbers] + - approximation of [reals] + - an approximate [equality_test] on expressions involving some reals Up: [mathematics] diff --git a/conjunctive_query b/conjunctive_query @@ -12,6 +12,7 @@ Subclasses: Generalization: - [conjunctive_query_signed] +- [conjunctive_query_inequalities] Up: [query_language] diff --git a/conjunctive_query_boolean b/conjunctive_query_boolean @@ -3,3 +3,5 @@ [conjunctive_query] with no [output_variable], all variables are [existentially_quantified] Up: [conjunctive_query], [query_boolean] + +Aliases: Boolean CQ, Boolean CQs diff --git a/conjunctive_query_diversity b/conjunctive_query_diversity @@ -1,6 +1,8 @@ # Conjunctive query diversity - [merkl2023diversity] +- [arenas2024towards] + - uses [ultrametrics] Up: [diversity] of [conjunctive_query] diff --git a/conjunctive_query_inequality b/conjunctive_query_inequality @@ -7,3 +7,5 @@ A [CQ] with [inequality_mathematics] Up: [conjunctive_query], [inequality_mathematics] See also: [query_with_negation] + +Aliases: CQ inequalities diff --git a/context_free_grammar_linear b/context_free_grammar_linear @@ -6,4 +6,4 @@ Testing [language_emptiness] of [intersection] is already [undecidable] by reduc Up: [context_free_grammar] -Aliases: linear grammar, linear grammars, linear context-free grammar, linear context-free grammars +Aliases: linear grammar, linear grammars, linear context-free grammar, linear context-free grammars, linear CFG, linear CFGs diff --git a/core b/core @@ -0,0 +1,21 @@ +# Core + +The [core] of an [instance] A is a [subinstance] B of A such that there is no [homomorphism] from B to a strict [subinstance] B' of B +- this is unique up to [isomorphism] +- it is equal to A if there is no [endomorphism] from A to a strict [subinstance] of A + +[computational_problem] of computing the core: +- checking if a [graph] is its own core + - clearly in [coNP] (guess the [homomorphism]) + - [conp_complete] + - https://cstheory.stackexchange.com/questions/2733/what-is-the-best-exact-algorithm-to-compute-the-core-of-a-graph +- checking if input [graph] G is core of input [graph] H + - is in [dp]: + - guess existence of [homomorphism] + - guess inexistence of other [homomorphism] + - is [dp_complete] by [fagin2005data2] + - https://cstheory.stackexchange.com/questions/2733/what-is-the-best-exact-algorithm-to-compute-the-core-of-a-graph + +Up: [homomorphism] + +See also: [chase_core] diff --git a/crpq b/crpq @@ -5,7 +5,7 @@ - [rpq] - [conjunctive_query] -Generalization: [conjunctive_context_free_path_query] +[Generalization]: [conjunctive_context_free_path_query] - [crpq_containment] diff --git a/cycle_rank b/cycle_rank @@ -2,6 +2,16 @@ https://en.wikipedia.org/wiki/Cycle_rank +The *cycle rank* of a [DAG] is 0 + +The *cycle rank* of a [directed_graph] which is not [strongly_connected_graph] is the [maximum] of the cycle rank of the [SCCs] + +The *cycle rank* of a [strongly_connected_graph] is 1 plus the [minimum] across all [vertices] v of the cycle rank of the [graph] obtained by [vertex_deletion] of v + +It is a kind of analogue of [tree_depth] but for [directed_graphs] instead of [undirected_graphs] + +The [computational_problem] of computing cycle rank is [NP_hard] + See also: [feedback_edge_number], [pathwidth_directed], [treewidth_directed], [circuit_rank], [strahler_number], [star_height], [eggans_theorem], [cycle] -Up: [width_measure] for [graph_directed] +Up: [width_measure] for [directed_graph] diff --git a/dagstuhl_semirings_val b/dagstuhl_semirings_val @@ -0,0 +1,24 @@ +# Dagstuhl semirings val + +by [val_tannen] about [semiring_provenance] + +shared an office with [Erich_Graedel] + +Mentions [Peter_Buneman] + +The [Orchestra] system for groups of scientists +- [Schema_mappings] +- when a database is updated, propagate the updates... + +[provenance_tracking] + +you have [provenance_tokens] X, and then Prov(X) is the set of [provenance_expressions] over the [provenance_tokens] +- features [product] for [conjunction] and [sum] for [disjunction] +- annotations 0 for "absent" and 1 for "untracked" + +Use [K_relations] for K = Prov(X) + +- [k_interpretation] +- [provenance_logic] + +Up: [dagstuhl_semirings_talks] diff --git a/database_instance b/database_instance @@ -0,0 +1,11 @@ +# Database instance + +A set of [relations] containing [tuples] or [facts], for the [relations] defined in a [relational_signature] + +[named_perspective] vs [unnamed_perspective] + +Up: [database_theory] + +Aliases: database + +See also: [instance] diff --git a/database_repairs b/database_repairs @@ -0,0 +1,16 @@ +# Database repairs + +A modification of a [database] to obtain a [database] which satisfies some [integrity_constraints] + +[repair_notions] + +[Computational_problems]: + +- [consistent_query_answering] +- [repair_counting] + +Up: [database_theory] + +See also: [language_repair], [graph_modification], [query_repairs], [data_cleaning] + +Aliases: database repair diff --git a/datalog_monadic b/datalog_monadic @@ -2,6 +2,8 @@ [Datalog] where all [intensional_predicates] are [monadic] +- [datalog_monadic_linear] + Up: [datalog] Aliases: Monadic Datalog diff --git a/degeneracy b/degeneracy @@ -3,7 +3,8 @@ https://en.wikipedia.org/wiki/Degeneracy_(graph_theory) An [undirected_graph] is k-degenerate if every [subgraph] has at least one [vertex] of [degree] at most k -- it does not make a difference whether we define this via [subgraphs] or via [induced_subgraphs], cf https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#Examples +- it does not make a difference whether we define this via [subgraphs] or via [induced_subgraphs] + - cf https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#Examples Special case: [2_degenerate_graphs] @@ -11,6 +12,13 @@ Some [enumeration] and [counting] problems on graphs have been studied based on Generalization to [relational_databases]: [partition_constraints] introduced in [deeds2025partition] +The [arboricity] is no greater than the degeneracy, and the degeneracy is at most twice the [arboricity]. + - source https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#Relation_to_other_graph_parameters + +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 + Up: [width_measure] -See also: [arboricity] +See also: [arboricity], [thickness] diff --git a/density_function b/density_function @@ -17,3 +17,5 @@ computing its regime on [context_free_languages]: [gawrychowski2010finding] Up: [automata] See also: [universality_automata], [sharp_automaton], [slice], [degree_of_ambiguity], [growth_rate_analysis] + +Aliases: density functions diff --git a/diameter b/diameter @@ -4,6 +4,8 @@ Definition : in a [graph], the longest distance of a [shortest_path] - [incremental_maintenance_diameter] +Diameter of [random_graphs]: [addarioberry2020diameter] + Up: [graph_radius_diameter] See also: [girth], [graph_coloring_diameter] diff --git a/dioid b/dioid @@ -1,16 +0,0 @@ -# Dioid - -Semiring where 1 + 1 = 1 -- Implies [idempotence]: x + x = x -- [natural_order]: x <= y si x + y = y - -Also called an "idempotent semiring" - -Freely generated dioid over a set of variables, with no coefficients: [bool_x] -- infinite [omega_chain]: 1 < 1 + z < 1 + z + z^2 < ... - -strenghtening: [semiring_absorptive] - -Up: [semiring] - -See also: [kleene_algebra] diff --git a/disjoint_union b/disjoint_union @@ -3,3 +3,5 @@ The [union] of two [sets] that are [disjoint] Up: [union] + +Aliases: disjoint unions diff --git a/downwards_closure b/downwards_closure @@ -0,0 +1,19 @@ +# 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 + +Given an [NFA], we can build in [linear_time] an [NFA] recognizing the upwards closure: cf [bachmeier2014finite] Lemma 8. +- this automaton is [weakly_acyclic_automaton] + +[downwards_closure_state_complexity] +- [downwards_closure_cfl_state_complexity] + +See also: [language_downwards_closed], [upwards_closure] + +Up: [formal_language_operator], [closure_operation] on [subsequences] + +Aliases: downward closure diff --git a/downwards_closure_cfl_state_complexity b/downwards_closure_cfl_state_complexity @@ -0,0 +1,9 @@ +# Downwards closure CFL state complexity + +We can construct [automata] recognizing the downwards closure of a [CFL]: cf [bachmeier2014finite]. +- As an [NFA], it can be done with an [exponential] set of [states], and there is also an [exponential] [lower_bound]. +- As a [DFA], it can be done with a [doubly_exponential] set of [states], and there is also a [doubly_exponential] [lower_bound] + +Up: [downwards_closure_state_complexity], [CFL] + +See also: [upwards_closure_cfl_state_complexity] diff --git a/downwards_closure_state_complexity b/downwards_closure_state_complexity @@ -0,0 +1,11 @@ +# Downwards closure state complexity + +- [karandikar2014state]: transforming a [DFA] to a [DFA] for the set of [subwords] has [exponential] [lower_bound] (not trivial) + - [lower_bound] on larger alphabet already in [okhotin2010state] +- [downwards_closure_cfl_state_complexity] + +Up: [downwards_closure], [state_complexity] + +Aliases: downward closure state complexity + +See also: [upwards_closure_state_complexity] diff --git a/dpll b/dpll @@ -0,0 +1,21 @@ +# DPLL + +https://en.wikipedia.org/wiki/DPLL_algorithm + +[algorithm] for [satisfiability_boolean] of [CNF] + +- if there is an empty clause, return UNSAT +- if there are no clauses, return SAT with current assignment +- if there is a clause containing a single [literal], instantiate that literal ([unit_propagation]) +- if there is a [literal_pure] aka one that occurs with only one polarity, insantiate that literal +- otherwise, select a literal ([branching_rule]), and explore first one polarity, then another + +Can be modified for [sharp_SAT], but: + +- not possible to handle [literal_pure] in a special way +- must explore both values of the chosen [literal], not just one +- must count [free_variables] + +Up: [algorithm] for [satisfiability_boolean] + +See also: [CDCL] diff --git a/dynamic_membership b/dynamic_membership @@ -0,0 +1,12 @@ +# Dynamic membership problem + +The [membership_problem] on [dynamic_data] + +- [dynamic_membership_word] +- [dynamic_membership_trees] + +[dynamic_membership_extensions] + +See also: [dynamic_complexity], [pattern_matching], [incremental_maintenance], [dynamic_data_word], [pattern_matching_dynamic] + +Up: [incremental_maintenance] diff --git a/dynamic_membership_regular b/dynamic_membership_regular @@ -0,0 +1,9 @@ +# Dynamic membership regular + +The [dynamic_membership] problem for [regular_languages] + +[Academic_papers]: +- [frandsen1997dynamic] +- [amarilli2021dynamic] + +Up: [dynamic_membership], [regular_language] diff --git a/dynamic_membership_word b/dynamic_membership_word @@ -0,0 +1,13 @@ +# Dynamic membership word + +- [dynamic_membership_regular] +- [incremental_maintenance_cfg] + +Depends on which [updates_word] are allowed + +[Generalizations]: +- [incremental_parsing] +- [dynamic_membership_restricted_edits] +- for [regular_expressions_counting]: [bjorklund2015succinct] + +Up: [dynamic_membership], [dynamic_word] diff --git a/dynamic_word b/dynamic_word @@ -0,0 +1,9 @@ +# Dynamic word + +A [word] on which we can apply [updates_word] + +- [dynamic_membership_word] + +Up: [word] + +Aliases: dynamic words, dynamic string, dynamic strings diff --git a/edge_deletion b/edge_deletion @@ -3,3 +3,7 @@ [koch2024edge] Up: [graph_modification] + +See also: [vertex_deletion] + +Aliases: edge removal diff --git a/edit_distance_operations b/edit_distance_operations @@ -0,0 +1,9 @@ +# Edit distance operations + +- [insertion] +- [deletion] +- [substitution] + +Up: [edit_distance], [update_word] + +See also: [levenshtein_distance] diff --git a/eggans_theorem b/eggans_theorem @@ -3,6 +3,6 @@ https://en.wikipedia.org/wiki/Star_height#Eggan's_theorem https://en.wikipedia.org/wiki/Cycle_rank#Star_height_of_regular_languages -[theorem]: The [star_height] of a [regular_language] L equals the minimum [cycle_rank] among all [automata_nondeterministic] with [epsilon_transition] accepting L. +[theorem]: The [star_height] of a [regular_language] L equals the minimum [cycle_rank] among all [NFA_epsilon] accepting L. Up: [theorem], [regular_language] diff --git a/ehrenfeucht_fraisse_game b/ehrenfeucht_fraisse_game @@ -0,0 +1,18 @@ +# EF-game + +Spoiler plays in [structure] A by marking a [vertex], Duplicator answers in [structure] B + +The structures induced by the [pebbles] must be [isomorphic] + +- Number of rounds necessary to distinguish both [structures] + - connections to types nombre de rounds nécessaires pour distinguer les deux structures ([quantifier_rank]) +- Number of [pebbles] needed + - connection to [FOk] + +[MSO] EF-game: the players can pebble sets + +Up: [logic], [games] + +See also: [bisimulation], [homomorphic_equivalence], [prover_verifier_game] + +Aliases: EF game, EF games diff --git a/empty_word b/empty_word @@ -0,0 +1,5 @@ +# Empty word + +The [word] with no [letters], having [length] 0 + +Up: [word] diff --git a/equation b/equation @@ -9,4 +9,4 @@ Up: [mathematics] -See also: [disequation], [inequation], [equality] +See also: [disequation], [inequation], [equality], [left_hand_side], [right_hand_side] diff --git a/exponentiation b/exponentiation @@ -1,8 +1,12 @@ # Exponentiation - [graph_exponentiation] -- [exponentiation_by_squaring] +- [exponentiation_by_squaring] or [fast_exponentiation] +- [squaring] +- [cubing] Up: [mathematics_operation] -See also: [exptime], [semigroup], [multiplication], [power_mathematics], [squaring], [square_root] +See also: [exptime], [semigroup], [multiplication], [power_mathematics], [square_root] + +Aliases: exponent, exponents diff --git a/factor b/factor @@ -1,9 +1,16 @@ # Factor -Definition: [word] u is factor of [word] v if we have v = xuy for some [word]s x and y +Definition: [word] u is factor of [word] v if we have v = xuy for some [words] x and y - [factor_universal] - [factorial_language] +- [absent_factor] + +If u is a factor of v, then v is an [extension] of u + +- [factor_closed_language] +- [factor_convex_language] +- [factor_free_language] Up: [formal_language_theory] diff --git a/factor_closed_language b/factor_closed_language @@ -0,0 +1,9 @@ +# Factor closed language + +A [formal_language] L such that, if u is in L and v is a [factor] of u, then v is in L + +Also closed "bifix-closed", because it is equivalent to being [prefix_closed] and [suffix_closed] + +Up: [factor] + +See also: [factor_convex_language], [Prefix_closed_language], [Suffix_closed_language], [factor_free_language], [bifix_free_language], [bifix_convex_language] diff --git a/fagins_theorem b/fagins_theorem @@ -0,0 +1,5 @@ +# Fagin's theorem + +https://en.wikipedia.org/wiki/Fagin%27s_theorem + +Up: [theorem], [descriptive_complexity] diff --git a/feferman_vaught_theorem b/feferman_vaught_theorem @@ -0,0 +1,11 @@ +# Feferman-Vaught theorem + +https://en.wikipedia.org/wiki/Feferman%E2%80%93Vaught_theorem + +[Theorem] in [model_theory] + +Within a certain [logic], relates the [theory] (the [set] of [satisfied] [formulas]) of a [direct_product] of [structures] to the [theory] of the individual [structures] + +A similar result exists for the [disjoint_union] of [structures]: [feferman_vaught_union] + +Up: [theorem], [logic] diff --git a/final_state b/final_state @@ -8,4 +8,4 @@ Up: [automata_concepts] Aliases: final states -See also: [nonfinal_state] +See also: [nonfinal_state], [initial_state] diff --git a/final_weight b/final_weight @@ -0,0 +1,9 @@ +# Final weight + +The [weight] in a [weighted_automaton] given to each [state] when ending a [run] at this state; in a non-weighted [automaton], the [final_states] would have weight 1 and the [nonfinal_states] would have weight 0 + +Can be represented as a [vector] of weights + +Up: [automata_weighted] + +Aliases: final weights diff --git a/finite_model_theory b/finite_model_theory @@ -2,6 +2,6 @@ - [finite_controllability] -Up: [logic], [finite] +Up: [model_theory], [finite] See also: [Open_world_query_answering] diff --git a/fp b/fp @@ -0,0 +1,5 @@ +# FP + +The [complexity_class] of the [functions] computed by [deterministic_Turing_machines] in [polynomial_time] + +Up: [complexity_class] diff --git a/fully_dynamic b/fully_dynamic @@ -0,0 +1,9 @@ +# Fully dynamic + +Refers to [dynamic_data] which allow [update] featuring both [insertion] and [deletion] of elements + +[survey_paper]: [hanauer2022recent] + +Up: [update] + +See also: [dynamic_data] diff --git a/function b/function @@ -20,6 +20,6 @@ Notions: Up: [mathematics] -See also: [functional_dependency] +See also: [functional_dependency], [function_symbol] Aliases: functions diff --git a/functional_dependency b/functional_dependency @@ -26,4 +26,4 @@ Up: [equality_generating_dependency] -Aliases: FD, FDs +Aliases: FD, FDs, functional dependencies diff --git a/functional_dependency_approximate b/functional_dependency_approximate @@ -1,8 +1,8 @@ # Functional dependency approximate -- Survey with real-world study: parciak2023measuring -- approximate implication: kenig2019integrity +- Survey with real-world study: [parciak2023measuring] +- approximate implication: [kenig2019integrity] Tags: #wikipedia -Up: [functional_dependency] +Up: [functional_dependency], [approximation] diff --git a/game_theory b/game_theory @@ -1,10 +0,0 @@ -# Game theory - -studies [games] - -- [shapley_value] -- [parity_games] et [pseudopolynomial]-time algorithm -- [muller_acceptance] -- [prisoners_dilemma] - -Up: [mathematics] diff --git a/gap_p b/gap_p @@ -0,0 +1,13 @@ +# GapP + +https://complexityzoo.net/Complexity_Zoo:G#gapp + +The functions that can be expressed as the [gap] of a [nondeterministic_Turing_machine], aka the difference between the number of [accepting_runs] and of [rejecting_runs] + +The closure of the [sharpP] functions under [subtraction] + +mentioned in [thierauf1994closure] for instance + +Up: [complexity_class] + +Aliases: GapP diff --git a/gate b/gate @@ -0,0 +1,11 @@ +# Gate + +A [vertex] of a [circuit], when seen as a [DAG] + +May be labeled by a [variable] for [variable_gates], or labeled by an [operator], e.g., [conjunction] or [disjunction] or [negation] for [Boolean_circuits] + +Up: [circuit] + +Aliases: gates + +See also: [wire] diff --git a/graph_bipartite b/graph_bipartite @@ -1,8 +1,9 @@ # Graph bipartite -Membership can be tested in [linear_time] with [greedy_algorithm] +Testing if a [graph] is bipartite can be done in [linear_time] with [greedy_algorithm] - [deficiency] +- [complete_bipartite_graph] Up: [graph_family] diff --git a/graph_isomorphism b/graph_isomorphism @@ -4,6 +4,6 @@ Up: [isomorphism] of [graph] -See also: [graph_homomorphism], [canonical_labeling], [weisfeiler_leman], [graph_automorphism] +See also: [graph_homomorphism], [canonical_labeling], [weisfeiler_leman], [graph_automorphism], [quantum_isomorphism] Aliases: graph isomorphic diff --git a/graph_modification b/graph_modification @@ -0,0 +1,14 @@ +# Graph modification + +An [update] on [graphs] + +- [edge_addition] +- [edge_deletion] + - [eulerian_edge_deletion] +- [vertex_deletion] + +- [graph_modification_problem] + +Up: [graph] + +See also: [graph_removal_lemma], [database_repairs] diff --git a/graph_modification_problem b/graph_modification_problem @@ -0,0 +1,8 @@ +# Graph modification problem + +[Computational_problems] that ask what is the minimum cost of performing [graph_modifications] on a [graph] to make it satisfy a property +- cf survey [crespelle2023survey] + +- for [treewidth]: [graph_modification_treewidth] + +Up: [graph_modification] diff --git a/graph_orientation b/graph_orientation @@ -5,3 +5,5 @@ - [constraint_graph_satisfiability] Up: [computational_problem] on [graph] + +Aliases: oriented diff --git a/graph_regular b/graph_regular @@ -0,0 +1,16 @@ +# Graph regular + +A [graph] where all [vertices] have the same [degree] + +https://mathoverflow.net/questions/428212/perfect-matching-decomposition-algorithm-for-bipartite-regular-graphs +- a [bipartite_graph] can be decomposed into edge-disjoint [perfect_matchings] iff the [graph] is regular +- uses [halls_theorem] https://math.stackexchange.com/questions/4361540/if-g-is-n-regular-then-g-has-n-disjoint-perfect-matchings + +[Special_case]: +- [2_regular] + +See also: [graph_matching_covered] + +Up: [graph] + +Aliases: regular graph 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/grid_graph b/grid_graph @@ -7,3 +7,5 @@ Up: [graph_family] See also: [wall_graph] + +Aliases: grid graphs diff --git a/homomorphism_equivalence b/homomorphism_equivalence @@ -0,0 +1,11 @@ +# Homomorphism equivalence + +A and B are homomorphically equivalent if there is a [homomorphism] from A to B and a [homomorphism] from B to A + +It is an [equivalence_relation]: [transitivity] is because the [composition] of two [homomorphisms] is a [homomorphism] + +Up: [homomorphism], [equivalence] + +See also: [minimization_conjunctive_query], [bisimulation] + +Aliases: homomorphic equivalence, homomorphically equivalent diff --git a/inconsistency b/inconsistency @@ -0,0 +1,5 @@ +# Inconsistency + +- [inconsistency_quantitative] + +Up: [uncertain_data] diff --git a/inconsistency_quantitative b/inconsistency_quantitative @@ -0,0 +1,13 @@ +# Inconsistency quantitative + +[Quantitative] measures of inconsistency ([constraint_violations]): + +- number of minimal inconsistent subsets +- number of tuples that participate to a violation +- minimal number of tuples to remove to satisfy the constraints + - see [database_repairs] and [subset_repairs] +- number of maximal consistent subsets + +Up: [inconsistency] + +See also: [database_repairs] diff --git a/independent_set b/independent_set @@ -33,4 +33,4 @@ See also: [matching], [vertex_cover] Up: [graph_substructure] -Aliases: coclique, anticlique +Aliases: coclique, anticlique, independent sets, cocliques, anticliques diff --git a/initial_state b/initial_state @@ -0,0 +1,9 @@ +# Initial state + +A [state] in an [automaton] in which a [run] can begin. A [DFA] has exactly one initial state, an [NFA] can have multiple initial states (but up to adding a superinitial state with [epsilon_transitions], and [eliminating_epsilon_transitions], it amounts to the same) + +Up: [automata_concepts] + +Aliases: initial states + +See also: [final_state], [nonfinal_state] diff --git a/initial_weight b/initial_weight @@ -0,0 +1,9 @@ +# Initial weight + +The [weight] in a [weighted_automaton] given to each [state] when beginning a [run] at this state; in a non-weighted [automaton], the [initial_states] would have weight 1 and the others would have weight 0 + +Can be represented as a [vector] of weights + +Up: [automata_weighted] + +Aliases: initial weights diff --git a/integers b/integers @@ -0,0 +1,9 @@ +# Integers + +The set \mathbb{Z} of [natural_numbers] or the [negative_numbers] (including [zero]) + +Up: [number] + +Aliases: integer, ZZ + +See also: [rational_numbers] diff --git a/integrity_constraint b/integrity_constraint @@ -10,3 +10,5 @@ See also: [logic] Up: [databases] + +Aliases: integrity constraints diff --git a/language_unary b/language_unary @@ -1,9 +1,9 @@ # Language unary -language over [unary_alphabet] +[Formal_language] over [unary_alphabet] Up: [formal_language] -Aliases: unary language +Aliases: unary language, unary languages See also: [density_function] diff --git a/language_upwards_closed b/language_upwards_closed @@ -0,0 +1,13 @@ +# 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]. + +Testing the [automaton_equivalence] of two [NFAs] recognizing downwards closed languages is [coNP_complete], cf [bachmeier2014finite] + +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/length b/length @@ -0,0 +1,7 @@ +# Length + +The number of [letters] of a [word] + +Generalization: [Parikh_image] + +Up: [word] diff --git a/locality_logic b/locality_logic @@ -0,0 +1,8 @@ +# Locality logic + +Works for [FO] + +- [Hanf's_theorem], cf [Hanf_normal_form] +- [Gaifman_normal_form] + +Up: [logic] diff --git a/locally_testable_language b/locally_testable_language @@ -1,20 +1,23 @@ # Locally testable language -A [formal_language] is locally testable if it is k-testable for some k, where a k-testable language is one where membership depends only on the prefix and suffix of length k and the set of infixes of size k +A [formal_language] is *locally testable* if it is k-testable for some k, where a k-testable language is one where membership depends only on the [prefix] and [suffix] of length k and the set of [factors] of size k ## Subclass -- "strictly locally testable" in [caron2000families]: the locally testable languages are the Boolean combinations of strictly locally testable languages +- "strictly locally testable" in [caron2000families]: the locally testable languages are the [Boolean_combinations] of [strictly_locally_testable_languages] ## Membership problem to the class -Membership is decidable in [ptime] with algebraic characterization, cf [schutzenberger1965monoids], [caron2000families] +The [membership_problem] is decidable in [PTIME] with an [algebraic_characterization], cf [schutzenberger1965monoids], [caron2000families] ## Generalizations - [locally_threshold_testable_language] where you can count infixes up to some threshold -- mTT+MOD dans place2013separating, where you can further count [modulo] a certain value +- mTT+MOD in [place2013separating], where you can further count [modulo] a certain value +- [garcia2000right]: [locally_testable_language_right] and [locally_testable_language_left], which strictly generalize the locally testable languages See also: [piecewise_testable_language], [local_language], [suffix_testable_language], [prefix_testable_language] Up: [formal_language] + +Aliases: locally testable languages diff --git a/logarithm b/logarithm @@ -6,3 +6,5 @@ Up: [mathematics] See also: [exponential], [logspace], [logarithmic] + +Aliases: logarithmic diff --git a/logcfl b/logcfl @@ -6,6 +6,8 @@ aka [nlogspace] with a [stack] Also: [logdcfl] for [deterministic_context_free_grammar] +[NL] is included in LOGCFL, and LOGCFL is included in [AC1], cf [buhrman2014computing] figure 1 + Up: [complexity_class] See also: [logcfl_complete] diff --git a/logic b/logic @@ -19,6 +19,7 @@ - [monadic_second_order_logic] - [separator_logic] - [description_logics] +- [LTL] ## Problems @@ -29,6 +30,7 @@ - [finite_model_theory] - [finite_controllability] +- [non_classical_logics] ## Tools @@ -66,6 +68,7 @@ - [quantifier_rank] - [logical_implication] - [sentence] +- [function_symbol] Up: [mathematics], [theoretical_computer_science] diff --git a/lower_bounds b/lower_bounds @@ -1,6 +1,7 @@ # Lower bounds -[complexity_lower_bounds] +- [complexity_lower_bounds] +- [conditional_lower_bound] Up: [computational_complexity] diff --git a/mathematics b/mathematics @@ -21,6 +21,7 @@ - [disequality] - [symmetry] - [composition] +- [number] ## Fields diff --git a/mathematics_basic_concepts b/mathematics_basic_concepts @@ -16,6 +16,7 @@ - [ring] - [field] - [homomorphism] +- [sum], [product] - [distance] - [vector] - [number] diff --git a/matrix b/matrix @@ -34,4 +34,10 @@ - [matrix_multiplication] - [matrix_mortality] +## [Generalizations] + +- [tensor] + Up: [mathematics] + +Aliases: matrices diff --git a/matrix_multiplication b/matrix_multiplication @@ -13,3 +13,5 @@ In specific [semirings]: Up: [multiplication] of [matrix] See also: [algorithm], [matrix_product] + +Aliases: matrix product diff --git a/maximum b/maximum @@ -3,6 +3,8 @@ the largest [element] of an [order] - [supremum] -See also: [minimum] +See also: [minimum], [maximization_problem] Up: [mathematics_basic_concepts] + +Aliases: max diff --git a/min_plus_product b/min_plus_product @@ -0,0 +1,7 @@ +# Min plus product + +The [matrix_product] but in the [tropical_semiring] + +See also: [mpp_minimum] + +Up: [operation] on [matrices] diff --git a/minimal_witness b/minimal_witness @@ -1,5 +1,7 @@ # Minimal witness +#todo "minimum 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 - [approximation]: find a subset of tuples giving the same results which is within a [approximation_multiplicative] factor of the size of the optimal subset diff --git a/minimum b/minimum @@ -8,3 +8,5 @@ The smallest element of an [order] Up: [mathematics_basic_concepts] See also: [maximum] + +Aliases: min diff --git a/monoid_positive b/monoid_positive @@ -0,0 +1,9 @@ +# Monoid positive + +A [monoid] being *positive* means x + y = 0 implies x = 0 and y = 0 + +aka "zero-sum-free" + +See also: [semiring_positive] + +Up: [monoid] diff --git a/natural_number b/natural_number @@ -0,0 +1,9 @@ +# Natural number + +The set \mathbb{N} of natural numbers + +Up: [number] + +Aliases: natural numbers, NN + +See also: [integers], [negative_numbers] diff --git a/naturally_ordered_semiring b/naturally_ordered_semiring @@ -3,3 +3,5 @@ [semiring] with [natural_order] Up: [natural_order], [semiring] + +Aliases: naturally ordered semirings, semiring naturally ordered diff --git a/negation b/negation @@ -9,4 +9,4 @@ Up: [logic] -Aliases: negated +Aliases: negated, negations diff --git a/network_reliability b/network_reliability @@ -2,6 +2,7 @@ - [st_reliability] - [network_reliability_fpras] +- [all_terminal_network_reliability] Up: [graph] diff --git a/neutral_element b/neutral_element @@ -0,0 +1,11 @@ +# Neutral element + +For S a [set] and e an [element], if you have a [operation] on S, then e is a neutral element if for every x in S, you have xe = ex = x. + +If there is a neutral element, then there is exactly one. + +When you have a [semigroup], you can add a neutral element if necessary and you get a [monoid]. + +Up: [algebra_basic_definitions] + +See also: [annihilating_element] diff --git a/nlogspace b/nlogspace @@ -1,6 +1,6 @@ # NL -[complexity_class] of [decision_problem] that can be solved by [nondeterministic] [turing_machine] with [logarithm] amount of memory +[complexity_class] of [decision_problems] that can be solved by [nondeterministic] [turing_machine] with [logarithmic] amount of memory Like [logspace] with [nondeterministic] diff --git a/nonfinal_state b/nonfinal_state @@ -0,0 +1,9 @@ +# Nonfinal state + +A [state] in an [automaton] which is not a [final_state] + +Up: [automata_concepts] + +See also: [final_state], [initial_state] + +Aliases: nonfinal states diff --git a/npmv b/npmv @@ -0,0 +1,5 @@ +# NPMV + +https://complexityzoo.net/Complexity_Zoo:N#npmv + +Up: [complexity_class] diff --git a/number b/number @@ -3,6 +3,7 @@ - [natural_number] - [diophantine_equation] - [sum_of_powers] +- [integers] - [rational_number] - [real_number] - [complex_number] diff --git a/parikhs_theorem b/parikhs_theorem @@ -4,4 +4,6 @@ https://en.m.wikipedia.org/wiki/Parikh's_theorem [regular_language] and [context_free_language] have same kind of [parikh_image] -Up: [parikh_image] +The [Parikh_image] of a [CFL] is a [union] of finitely many [linear_sets], where a [linear_set] is an expression of the form u + M alpha over alpha the vectors with integer values, for u an origin vector and M a [matrix] + +Up: [theorem] about [parikh_image] diff --git a/parity_p b/parity_p @@ -6,4 +6,4 @@ https://en.wikipedia.org/wiki/Parity_P Up: [parity], [complexity_class] -See also: [parity_fine_grained] +See also: [parity_fine_grained], [Z_2Z] diff --git a/partial_run b/partial_run @@ -0,0 +1,5 @@ +# Partial run + +A generalization of [runs], that only process a [prefix] of the input [word] + +Up: [run] diff --git a/pattern_matching b/pattern_matching @@ -21,6 +21,7 @@ - [point_set_pattern_matching] - [approximate_pattern_matching] - [maximal_exact_match] +- [internal_pattern_matching] ## Generalizations diff --git a/polynomial b/polynomial @@ -3,8 +3,21 @@ - [polynomial_equation] - [lagrange_interpolation] -Up: [mathematics] +Types: + +- [polynomial_homogeneous] +- [polynomial_multivariate] + - [polynomial_multilinear] +- [polynomial_irreducible] +- [polynomial_factored] +- [polynomial_expanded] + +Concepts: -See also: [polynomial_irreducible] +- [monomial] +- [polynomial_degree] +- [root] + +Up: [mathematics] Aliases: polynomials diff --git a/polynomial_hierarchy b/polynomial_hierarchy @@ -1,8 +1,9 @@ # Polynomial hierarchy (PH) -- first levels: [nptime], [conptime] +- first levels: [NPtime], [coNPtime] - see also [np_cap_conp] - second level: [pi2], [sigma2] + - [Pi2_complete], [Sigma2_complete] - see also [pi2_cap_sigma2] - [delta2p] = [ptime] with an [nptime] [oracle] - https://complexityzoo.net/Complexity_Zoo:D#delta2p diff --git a/posbool b/posbool @@ -0,0 +1,7 @@ +# PosBool + +Like [why_provenance], but imposing [absorptivity] + +Corresponds to [Boolean_formulas_positive] over the set of [provenance_tokens] seen as [variables] + +Up: [why_provenance] diff --git a/possible_answers b/possible_answers @@ -0,0 +1,9 @@ +# Possible answers + +Given a [query] Q and [uncertain_data] D, a *possible answer* is a [query_answer] which is true on some [possible_world] of D. + +See also: [certain_answers] + +Up: [uncertain_data] + +Aliases: possible answer diff --git a/pqe_ucq b/pqe_ucq @@ -0,0 +1,11 @@ +# PQE for UCQ + +- [dichotomy]: [dalvi2012dichotomy] +- new presentation: [kenig2020dichotomy] + +The complexity in the [query] of the [meta_dichotomy] criterion is open + - cf [amarilli2020dichotomy] which says so explicitly + +Up: [pqe] for [union_of_conjunctive_queries] + +See also: [pqe_unsafe] diff --git a/prefix b/prefix @@ -3,6 +3,9 @@ - [prefix_u1] - [prefix_code] - [prefix_suffix_query] +- [prefix_closed_language] +- [prefix_convex_language] +- [prefix_free_language] Up: [formal_language_theory] diff --git a/prefix_closed_language b/prefix_closed_language @@ -0,0 +1,9 @@ +# Prefix closed language + +A [formal_language] where, if v is in L and u is a [prefix] of v, then u is in L + +Up: [prefix] + +Aliases: language prefix closed + +See also: [suffix_closed_language], [prefix_convex_language] diff --git a/prefix_free_language b/prefix_free_language @@ -0,0 +1,9 @@ +# Prefix free language + +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 + +Up: [prefix] + +See also: [suffix_free_language], [bifix_free_language] + +Aliases: prefix free diff --git a/probabilistic_database_model b/probabilistic_database_model @@ -1,8 +1,10 @@ # Probabilistic database model -- [tuple_independent_database] -- [block_independent_disjoint] [database] +- [tuple_independent_database] (TID) +- [block_independent_disjoint] [database] (BID) - [pc_table] - also: [probabilistic_xml] +Relevant source: "Uncertain Data Models", [Encyclopedia_of_Database_Systems], page numbered 4297 + Up: [probabilistic_databases], [database_model] diff --git a/probabilistic_database_neighboring_fields b/probabilistic_database_neighboring_fields @@ -0,0 +1,10 @@ +# Probabilistic database neighboring fields + +- [graphical_models] +- [knowledge_compilation] +- other [uncertain_data] / [incomplete_data] + - recent survey on incomplete data: [console2020coping] +- [network_reliability] problem ([all_terminal_network_reliability], etc.) +- [shapley_value] computation or [query_resilience] ([reshef2020impact]) and other such measures + +Up: [probabilistic_databases] diff --git a/probabilistic_databases b/probabilistic_databases @@ -0,0 +1,30 @@ +# Probabilistic databases + +- [probabilistic_database_model], +- [probabilistic_database_neighboring_fields] +- [provenance] / [lineage] + - [semirings] + - tractable [circuit] representations + - lower bounds from [amarilli2019connecting] +- [probabilistic_query_evaluation] + - [self-join-free_CQs] + - [UCQs]: [pqe_ucq] [dalvi2012dichotomy] + - [q9_conjecture]: [monet2020solving] + - [recursive_queries]: [amarilli2020dichotomy] +- [pqe_treelike] + - [pqe_MSO], via [provenance_circuits] + - historical motivation: [probabilistic_XML] + - [lower_bounds] in [amarilli2016tractable] +- [pqe_combined] +- [pqe_unweighted] + - [kenig2020dichotomy] + - [amarilli2022uniform] + - [symmetric_model_counting] +- [pqe_new_directions] + +- [pqe_applications] +- [probabilistic_databases_practice] + +See also: [relational_algebra], [relational_calculus] + +Up: [database_theory] diff --git a/provenance b/provenance @@ -0,0 +1,42 @@ +# Provenance + +https://en.wikipedia.org/wiki/Data_lineage#Data_provenance + +foundational [academic_paper]: [green2007provenance], using [semiring], i.e., [semiring_provenance] + +Uses of provenance: +- [uncertainty] + - [pqe] +- [reasoning] +- [explanation] + +In various settings, e.g., [query_languages] and [types_of_data]: +- For [Datalog]: [provenance_datalog] +- For [reasoning]: [provenance_reasoning] +- For [description_logics]: [provenance_description_logics] +- For [logic]: [provenance_logic] +- For [games]: [provenance_games] +- For [CQs]: [provenance_optimal_joins] + - Specifically for [triangles]: [provenance_triangle] +- On [treelike_data]: [provenance_treelike_data] + +Formalisms: +- [provenance_expression] +- [provenance_circuit] + +Kinds of provenance: +- [provenance_semirings] + - [why_provenance] +- [where_provenance] + +[Computational_problems]: +- [provenance_computation] + +[Research_questions]: +- [provenance_size] + +- [provenance_practical] + +See also: [explainability], [artificial_intelligence_explainable], [pqe] + +Up: [research] diff --git a/provenance_circuit b/provenance_circuit @@ -6,3 +6,5 @@ Can use [circuit] for [provenance], e.g., - [provenance_mso]: [monadic_second_order_logic] provenance [amarilli2015provenance] Up: [provenance], [circuit] + +Aliases: provenance circuits diff --git a/provenance_datalog b/provenance_datalog @@ -0,0 +1,16 @@ +# Provenance for Datalog + +Computing [provenance] for [Datalog] [queries] + +Subcases: +- [provenance_stratified_datalog] + +[Academic_papers]: + +- [bourgaux2022revisiting] gives several different definitions +- [calautti2024below]: computing [why_provenance] + - computing [whyminimal_provenance] and [whymultiplicity_provenance] + - [calautti2023complexity]: [provenance_membership_testing] +- [convergence] for [datalog]: [abokhamis2021convergence] + +Up: [provenance], [datalog] diff --git a/provenance_optimal_joins b/provenance_optimal_joins @@ -1,5 +1,8 @@ # Provenance for optimal joins -- wang2022query, achieves [polymatroid] bound +Building [provenance_circuits] during [query_evaluation]: see [wang2022query] + - achieves [polymatroid] bound Up: [optimal_joins] with [provenance] + +See also: [PANDA] diff --git a/provenance_panda b/provenance_panda @@ -1,5 +0,0 @@ -# Provenance for PANDA - -see [wang2022query] - -Up: [provenance] for [panda] diff --git a/pseudoarboricity b/pseudoarboricity @@ -0,0 +1,10 @@ +# Pseudoarboricity + +https://en.wikipedia.org/wiki/Pseudoforest#Algorithms + +The minimum number of [pseudoforests] in which the [edges] of an [undirected_graph] can be partitioned, or the minimum k such that the [edges] can be [oriented] to form a [directed_graph] with [outdegree] at most k +- can be computed in [PTIME] + +See also: [arboricity] + +Up: [width_measure] diff --git a/pseudoforest b/pseudoforest @@ -0,0 +1,11 @@ +# Pseudoforest + +https://en.m.wikipedia.org/wiki/Pseudoforest + +[Undirected_graph] in which every [connected_component] has at most one [cycle] + +Up: [forest] + +Aliases: pseudoforests + +See also: [pseudoarboricity] diff --git a/ptime b/ptime @@ -13,4 +13,4 @@ Up: [complexity_class] See also: [pseudo_polynomial_time], [quasipolynomial], [oplusp], [ptime_reduction] -Aliases: P +Aliases: P, polynomial time diff --git a/pushdown_automaton b/pushdown_automaton @@ -8,6 +8,10 @@ - introduced in [ginsburg1966finite] - mentioned in [ganardi2018sliding] +- [universality_automata_pushdown] + Up: [stack_automata] See also: [visibly_pushdown_automaton] + +Aliases: pushdown automata diff --git a/quantifier b/quantifier @@ -0,0 +1,12 @@ +# Quantifier + +- [existential_quantifier] +- [universal_quantifier] + +- [quantifier_rank] + +Up: [logic] + +See also: [QBF] + +Aliases: quantification diff --git a/quantitative b/quantitative @@ -0,0 +1,5 @@ +# Quantitative + +- [quantitative_mso] + +Up: [logic] diff --git a/query_recursive b/query_recursive @@ -8,3 +8,5 @@ Up: [query_language] Aliases: recursive query, recursive queries + +See also: [query_nonrecursive] diff --git a/query_with_negation b/query_with_negation @@ -0,0 +1,9 @@ +# Query with negation + +[query] featuring [negation] + +- [conjunctive_query_signed] + +Up: [query], [negation] + +Aliases: queries negation, query negation, query negations 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/regular_expression_extensions b/regular_expression_extensions @@ -1,7 +1,8 @@ # Regular expression extensions -- [regular_expression_conjunction] -- [regular_expression_negation] +- [regular_expression_extended] + - [regular_expression_conjunction] + - [regular_expression_negation] - [capture_variables] - [regex], with [back_references] - see [freydenberger2019deterministic] diff --git a/rejecting_run b/rejecting_run @@ -0,0 +1,9 @@ +# Rejecting run + +A [run] which finishes at a [nonfinal_state] + +See also: [accepting_run] + +Up: [run] + +Aliases: rejecting runs diff --git a/repair_notions b/repair_notions @@ -0,0 +1,7 @@ +# Repair notions + +- [subset_repair] +- [optimal_subset_repair], a [subset_repair] that [optimizes] a cost +- can also do [insertions] of [tuples] in some cases + +Up: [database_repairs] diff --git a/representation_system b/representation_system @@ -0,0 +1,11 @@ +# Representation system + +A way to represent *uncertain data*: you have [representations], and each representation is a concise representation of a set of [possible_worlds]. For instance: + +- [NULLs] +- [v_tables] +- [c_tables] + +Presented in [imielinski1984incomplete] + +Up: [uncertain_data] 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/run b/run @@ -0,0 +1,11 @@ +# Run + +A [sequence] of [states] that starts by an [initial_state] and follows [configurations] on an input [word] + +- [accepting_run] +- [rejecting_run] +- [partial_run] + +Up: [automata_concepts] + +Aliases: runs diff --git a/second_order_logic b/second_order_logic @@ -0,0 +1,14 @@ +# SO + +- [monadic_second_order_logic] +- [descriptive_complexity]: correspondence with [polynomial_hierarchy] + - [existential_second_order_logic] corresponds to [nptime], etc., + [quantifier_prefix] +- [second_order_transitive_closure] SO(TC) [ferrarotti2018expressivity] + - corresponds to [pspace] + - can express [hamiltonian_cycle] + - which is known not to be expressible in [monadic_second_order_logic] + +See also: [first_order_logic] + +Aliases: SO diff --git a/semiring_absorptive b/semiring_absorptive @@ -0,0 +1,15 @@ +# Absorptive semiring + +A [semiring] where you have 1 + a = 1 for every a + +Implies [semiring_idempotence] + +[absorptive_semiring_notes] + +Generalization: [semiring_p_stable] + +Up: [dioid] + +See also: [absorptivity] + +Aliases: absorptive semiring, absorptive semirings diff --git a/semiring_circuit b/semiring_circuit @@ -0,0 +1,10 @@ +# Semiring circuit + +A [circuit] whose [gates] correspond to [operations] in a specific [semiring] + +Special cases: + +- [Boolean_circuit] +- [Arithmetic_circuit] + +Up: [circuit] diff --git a/semiring_idempotent b/semiring_idempotent @@ -1,5 +1,8 @@ # Idempotent semiring -A [semiring] satisfying the equation a+a = a for every a +- [semiring_additively_idempotent] +- [semiring_multiplicative_idempotent] Up: [semiring], [idempotent] + +Aliases: semiring idempotence, idempotent semiring, idempotent semirings diff --git a/semiring_list b/semiring_list @@ -0,0 +1,28 @@ +# Semiring examples + +- The [Boolean_semiring] + +- The [natural_numbers] + - useful for [bag_semantics] in [query_evaluation] + +- The [universal_semiring], and its variants + - [bool_x] losing coefficients ([sets] of [bags]) + - [semiring_absorptive]: adding [absorptivity] + - [Trio] semiring: losing exponents ([bags] of [sets]) + - [Why_provenance] losing coefficients and exponents ([sets] of [sets]) + - [PosBool] imposing [absorptivity], + - And losing exponents relative to [semiring_absorptive] + - [Which_provenance]: just a [set] + +- The [min_max_semiring]: (A, [max], [min], 0, 1) + - in particular [access_control_semiring] and [fuzzy_semiring] + +- The [Viterbi_semiring], aka the confidence semiring +- The [tropical_semiring] +- The [fuzzy_semiring] + +- Any [ring] + +- [semiring_examples_others] + +Up: [semiring] diff --git a/semiring_multiplicative_idempotent b/semiring_multiplicative_idempotent @@ -0,0 +1,7 @@ +# Semiring multiplicative idempotent + +[Semiring] where s s = s for all s, i.e., [multiplicatively_idempotent] + +Generalization: [semiring_n_idempotent] + +Up: [semiring_idempotent] diff --git a/semiring_n_idempotent b/semiring_n_idempotent @@ -0,0 +1,7 @@ +# Semiring n idempotent + +[Semiring] where s^n s = s^n + +Special case: [semiring_multiplicative_idempotent] + +Up: [semiring] diff --git a/semiring_provenance b/semiring_provenance @@ -0,0 +1,11 @@ +# Semiring provenance + +[Provenance] of [queries] using [semirings] to cover multiple use cases + +Foundational paper: [green2007provenance] + +For [query_optimization], you need the [semiring] to be [semiring_commutative] + +Up: [provenance], [semirings] + +See also: [provenance_polynomial] diff --git a/sequence b/sequence @@ -5,6 +5,8 @@ - [Kleene_sequence] - [De_Bruijn_sequence] - [arithmetic_progression] +- [hailstone_sequence] +- [Recamans_sequence] ## Concepts diff --git a/single_source_shortest_path b/single_source_shortest_path @@ -1,5 +1,6 @@ # Shortest path single source -[single_source_shortest_path_algorithm] +- [single_source_shortest_path_algorithm] + - [single_source_shortest_path_faster] Up: [shortest_path] diff --git a/sjfcq b/sjfcq @@ -1,7 +1,9 @@ # SJFCQ -[conjunctive_query] without [self_join] +[conjunctive_query] without [self_joins] [dichotomy] for [pqe] in [dalvi2007efficient] Up: [conjunctive_query], [self_join] + +Aliases: self join free CQ, self join free CQs, selfjoin free CQ, selfjoin free CQs, cq self join free, cqs self join free, self-join-free CQ, self-join-free CQs diff --git a/spanl b/spanl @@ -4,6 +4,8 @@ Counting the number of *distinct* outputs of an [nl] [transducer] Complete problem: [sharp_nfa] +Defined in [alvarez1993very] + See also: [spanp] Up: [complexity_class], [counting] diff --git a/state b/state @@ -4,6 +4,9 @@ An [automaton] consists of a set of states, which is generally finite. - [initial_state] - [final_state] +- for [alternating_automata] + - [existential_state] + - [universal_state] Up: [automata_concepts] diff --git a/state_complexity b/state_complexity @@ -0,0 +1,13 @@ +# State complexity + +https://en.wikipedia.org/wiki/State_complexity + +- For [automaton_complement] of an [automaton] with n [states] on a binary alphabet you may need 2^n states +- [minimization] / [canonical_automata] + - for [DFAs]: can be done in [PTIME] + - (quibble about whether it should be [complete_automata] or not) + - for [NFAs]: [pspace]-complete +- [upward_closure_state_complexity] +- [downward_closure_state_complexity] + +Up: [automata] diff --git a/strongly_connected_component b/strongly_connected_component @@ -9,4 +9,4 @@ Up: [graph] See also: [biconnected_component], [connected_component], [strongly_connected] -Aliases: SCC, strongly connected components +Aliases: SCC, strongly connected components, SCCs diff --git a/subsequence b/subsequence @@ -15,8 +15,11 @@ - [longest_common_supersequence] [timkovsky1989complexity] - [longest_increasing_subsequence] - [p_subsequence] +- [subsequence_automaton] +- [absent_subsequence] +- [subsequence_order] -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/subword b/subword @@ -8,6 +8,9 @@ must be contiguous, unlike [subsequence] - [longest_common_subword] [timkovsky1989complexity] - [shortest_common_superword] [timkovsky1989complexity] +- [subword_closed_language] +- [subword_free_language] +- [subword_convex_language] Up: [formal_language_theory] diff --git a/suffix b/suffix @@ -5,6 +5,8 @@ - [suffix] - [suffix_free_language] - [suffix_testable_language] +- [suffix_closed_language] +- [suffix_convex_language] Up: [formal_language_theory] diff --git a/suffix_closed_language b/suffix_closed_language @@ -0,0 +1,7 @@ +# Suffix closed language + +A [formal_language] where, if u is in L and v is a [suffix] of u, then v is in L + +Up: [suffix] + +See also: [Prefix_closed_language], [suffix_convex_language] diff --git a/suffix_free_language b/suffix_free_language @@ -0,0 +1,9 @@ +# Suffix free language + +A [formal_language] L is *suffix-free* if, whenever u and v are in L and u is a [suffix] of v, then u = v + +Up: [suffix] + +See also: [prefix_free_language], [bifix_free_language] + +Aliases: suffix free 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/synchronizing_word b/synchronizing_word @@ -4,4 +4,4 @@ Up: [automata] -See also: [mortal_word], [meeting_time] +See also: [mortal_word], [meeting_time], [synchronizing_sets] diff --git a/tdta b/tdta @@ -0,0 +1,21 @@ +# tDTA + +Defined by a set of [states], an [initial_state], a set of [final_states], and a [transition_function] describing the state of the children of each tree node as a function of the state of the node and the label of the node. + +[acceptance_condition]: all [leaves] are labeled with a [final_state] + +The [tree_languages] that can be recognized by tDTAs are a proper subset of the [regular_tree_languages] +- In particular, if such an automaton accepts f(a,b) and f(a',b') then they accept f(a,b') and f(a',b) + +To understand the [expressive_power] of such [automata]: they only depend on the [word_language] of the [paths] from the [root] to the [leaves] in the input [tree] +- A [tree] t is accepted by a tDTA A if and only if the set of root-to-leaf [paths] of t is included in the set of root-to-leaf paths of the [trees] accepted by A + +Membership to the class of languages recognized by tDTAs is [decidable]. Generalization: [Boolean_closure_tDTA] + +Generalization: [tDTA_set_acceptance] + +Up: [tree_automaton_top_down], [automata_deterministic] + +See also: [bDTA], [tNTA], [tUTA] + +Aliases: deterministic top-down tree automaton diff --git a/theorem b/theorem @@ -6,6 +6,7 @@ A [result] in [mathematics], recognized as challenging to prove - [Brook's_theorem] - [Buchi's_theorem] - [Chen's_theorem] +- [Codd's_theorem] - [Context_free_grammar_pushdown_automaton_equivalence] - [Courcelle_theorem] - [Eggan's_theorem] @@ -22,6 +23,7 @@ A [result] in [mathematics], recognized as challenging to prove - [Ladner's_theorem] - [Mantel's_theorem] - [Menger's_theorem] +- [Nicomaque's_theorem] - [Parikh's_theorem] - [Prime_number_theorem] - [Ramsey_theorem] diff --git a/transient_state b/transient_state @@ -0,0 +1,5 @@ +# Transient state + +terminology in [ganardi2024regular] for [states] that cannot be reached from themselves + +Up: [state] diff --git a/tree_automaton b/tree_automaton @@ -5,9 +5,7 @@ Defines [regular_tree_language] ## Types - [tree_automaton_bottom_up] -- [tree_automaton_top_down]: - - [automata_deterministic] leads to a weaker class of languages - - [unambiguous]: is the same as unambiguous bottom-up (the unambiguity condition is symmetric) +- [tree_automaton_top_down] ## Variants @@ -21,3 +19,5 @@ and [jumping_automata_on_graphs] jumping automata on graphs Up: [automata] on [tree] See also: [dtd], [xml] + +Aliases: tree automata diff --git a/tree_automaton_bottom_up b/tree_automaton_bottom_up @@ -0,0 +1,12 @@ +# Tree automaton bottom up + +- [initialization_function] / [initialization_relation] +- [transition_function] / [transition_relation] + +types: + +- [automaton_deterministic]: [bDTA] +- [automaton_unambiguous]: [bUTA] +- [automaton_nondeterministic]: [bNTA] + +Up: [tree_automaton], [bottom_up] diff --git a/tree_automaton_top_down b/tree_automaton_top_down @@ -0,0 +1,12 @@ +# Tree automaton top down + +- [automata_deterministic]: [tDTA] + - leads to a weaker class of languages + - [Boolean_closure]: [Boolean_closure_tDTA] +- [unambiguous]: [tUTA] + - has same [expressiveness] as [bUTA] + - (the unambiguity condition is symmetric) +- [nondeterministic]: [tNTA] + - has same [expressiveness] as [bNTA] + +Up: [tree_automaton] diff --git a/tropical b/tropical @@ -0,0 +1,7 @@ +# Tropical + +- [tropical_semiring] + +Named after https://en.wikipedia.org/wiki/Imre_Simon + +Up: [mathematics] diff --git a/tropical_semiring b/tropical_semiring @@ -0,0 +1,15 @@ +# Tropical semiring + +The [semiring] defined with [min] and [plus] + +Intuition: you want the derivation with least cost ([min]), and joint use of values means you pay for both ([plus]) + +Useful for [shortest_path] in [graphs] + +It is an [absorptive_semiring] + +Up: [semiring_list] + +See also: [mpp_minimum], [tropical], [max_plus_semiring] + +Aliases: semiring tropical diff --git a/turing_machine b/turing_machine @@ -14,6 +14,7 @@ ## Variants - [turing_machine_symmetric] +- [turing_machine_weighted] ## Resources @@ -22,3 +23,5 @@ Up: [theoretical_computer_science] See also: [ram_model], [church_turing_thesis], [alan_turing], [pushdown_automaton], [turing_complete], [decidability], [recursively_enumerable], [kolmogorov_complexity] + +Aliases: Turing machines diff --git a/turing_machine_deterministic b/turing_machine_deterministic @@ -0,0 +1,11 @@ +# Turing machine deterministic + +A [turing_machine] whose [transition_relation] is a [transition_function], so that it has at most one [run] on every input + +- [turing_machine_deterministic_ptime] + +Up: [turing_machine] + +Aliases: deterministic Turing machine, deterministic Turing machines + +See also: [turing_machine_nondeterministic] diff --git a/turing_machine_nondeterministic b/turing_machine_nondeterministic @@ -1,7 +1,11 @@ # Turing machine nondeterministic +A [Turing_machine] which may have several applicable [transitions], so that it can have multiple [runs] on an input + - [nptime]: [nondeterministic_ptime_turing_machine] Up: [turing_machine] Aliases: nondeterministic Turing machine + +See also: [turing_machine_deterministic] diff --git a/turing_machine_weighted b/turing_machine_weighted @@ -0,0 +1,14 @@ +# Turing machine weighted + +[turing_machine_weighted_definition] + +They are to [Turing_machines] what [weighted_automata] are to [automata] + +Can define [complexity_classes] that are [formal_power_series]: [weighted_language_series_correspondence] +- see also [weighted_complexity_classes] in [badia2024logical] + +Were originally called "algebraic turing machines" in [damm2002complexity], connected to [weighted_automata] in [kostolanyi2023weighted] + +Up: [turing_machine], [weighted] + +Aliases: Weighted Turing machine, weighted Turing machines diff --git a/uc2rpq b/uc2rpq @@ -1,11 +1,11 @@ # UC2RPQ -[query_union] of [C2RPQs] +A [query] which is a [disjunction] of [C2RPQs] Studied for such [queries]: - [semantic_acyclicity] - [figueira2024semantic] - - [feier2024evaluating]: article on [treewidth] and + - [feier2024evaluating]: article on [treewidth] Up: [graph_query_languages], [c2rpq], [union_of_conjunctive_queries] diff --git a/uncertain_data b/uncertain_data @@ -2,5 +2,9 @@ - [inconsistency] - [certain_answers] +- [possible_answers] +- [representation_system] +- [consistent_query_answering] +- [open_world_query_answering] Up: [probabilistic_databases] diff --git a/union b/union @@ -2,5 +2,6 @@ - [union_trick] - [disjoint_union] +- [language_union] Up: [set_theory], [boolean_operator] diff --git a/universal_semiring b/universal_semiring @@ -1,10 +1,10 @@ # Universal semiring -N[X], [semiring] of [polynomial]s with [variable]s X +[NN][X ], [semiring] of [polynomials] with [variables] X - [universality_property] -- [commutation_under_homomorphism]s +- [commutation_under_homomorphisms] Up: [semiring_list] -See also: [power_series] +See also: [power_series], [provenance_polynomial] diff --git a/universality_automata b/universality_automata @@ -4,6 +4,7 @@ - [universality_automata_nondeterministic]: [conp_complete] - [universality_automata_deterministic]: [ptime] +- [universality_automata_pushdown] - [factor_universal] - [subword_universal] diff --git a/universality_automata_deterministic b/universality_automata_deterministic @@ -1,6 +1,8 @@ # Universality automata deterministic -in [ptime] via [automaton_complementation] +In [ptime] via [automaton_complementation] + +Generalizes to [universality_automata_pushdown_deterministic] Up: [universality_automata], [automaton_deterministic] diff --git a/update b/update @@ -7,7 +7,7 @@ Kinds of updates supported for [dynamic_data]: - [substitution] - [insertion] - [deletion] -- For [dynamic_data_graph]: [update_graph] +- For [dynamic_data_graph]: [graph_modification] - [edge_addition] - [edge_deletion] - In general diff --git a/update_word b/update_word @@ -11,4 +11,6 @@ Up: [update] for [word] +See also: [dynamic_word], [edit_distance_operations] + Aliases: updates word diff --git a/vertex_deletion b/vertex_deletion @@ -0,0 +1,5 @@ +# Vertex deletion + +Removing a [vertex] from a [graph], and doing [edge_removal] of all [edges] that are [incident] to the removed [vertex] + +Up: [graph_modification] diff --git a/viterbi_semiring b/viterbi_semiring @@ -0,0 +1,11 @@ +# Viterbi semiring + +The [semiring] defined as ([0, 1], [max], [multiplication], 0, 1) + +Intuitively: you want the derivation with highest confidence ([max]), and when you use several values simultaneously then confidence decreases via [multiplication] + +It is an [absorptive_semiring] + +Up: [semiring_list] + +See also: [tropical_semiring] diff --git a/which_provenance b/which_provenance @@ -0,0 +1,5 @@ +# Which provenance + +The [set] of [provenance_tokens] that intervene in the answers ([flattens] [conjunction] and [disjunction]) + +Up: [semiring_list] diff --git a/why_provenance b/why_provenance @@ -0,0 +1,9 @@ +# Why provenance + +[Semiring_provenance] in the [semiring] of [sets] of [sets] of [provenance_tokens] + +Specialization: [PosBool] + +- [why_provenance_computation] + +Up: [provenance] diff --git a/why_provenance_computation b/why_provenance_computation @@ -0,0 +1,5 @@ +# Why provenance computation + +- [calautti2024computing] via [sat_solver] + +Up: [provenance_computation] for [why_provenance] diff --git a/word b/word @@ -5,20 +5,25 @@ Finite [sequence] of [letters] - [primitive_word] - [twin] -generalization: +Quantities: +- [length] + +Generalizations: - [data_word] +- [dynamic_word] -operation: +Operations: - [concatenation] - [primitive_root] - [mirror] -type: +Special cases: - [palindrome] - [square_word] +- [empty_word] Up: [formal_language_theory] -See also: [update_word], [empty_word], [sequence], [dynamic_word] +See also: [update_word], [sequence] -Aliases: words +Aliases: words, string, strings