commit bb4c47dac2cbc9dc606e4f81df2ee4b73b61e50c parent 79f9218af05c2d525febb0283b65c217784d5b8c Author: Antoine Amarilli <a3nm@a3nm.net> Date: Thu, 6 Mar 2025 20:58:46 +0100 Merge branch 'master' of a3nm.net:git/wiki_research Diffstat:
324 files changed, 2245 insertions(+), 227 deletions(-)
diff --git a/2_regular b/2_regular @@ -0,0 +1,5 @@ +# 2 regular + +A 2-regular graph is a [disjoint_union] of [cycles] + +Up: [graph_regular] 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/aggregation b/aggregation @@ -1,5 +1,7 @@ # Aggregation +- [queries_aggregate] + See also: [quantile], [median], [mean], [sum] Up: [database_theory] 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] @@ -25,8 +25,12 @@ Applications: Notion of [reduction]: [approximation_preserving_reduction] -Other notion: [query_approximation] +Other notions: + +- [query_approximation] +- [approximate_aggregation] +- [query_evaluation_approximate] Up: [research_directions] -Aliases: approximate counting +Aliases: approximate counting, approximated diff --git a/approximation_class b/approximation_class @@ -1,10 +1,10 @@ # Approximation classes -- FPRAS [fpras]: for all epsilon you have an [algorithm_randomized] running in polynomial time in 1/e and in the input, with a probability delta of failure +- [FPRAS]: for all epsilon you have an [algorithm_randomized] running in polynomial time in 1/e and in the input, with a probability delta of failure - variant QPRAS [qpras] with "quasi-polynomial time" [quasipolynomial] -- PRAS [pras]: same but not polynomial in 1/e -- without R, a deterministic algorithm (PRAS vs PTAS [ptas], FPRAS vs FPTAS [fptas]) -- APX [apx]: there is an approximation algorithm for a certain fixed epsilon +- [PRAS]: same but not polynomial in 1/e +- without R, a deterministic algorithm (PRAS vs [PTAS], FPRAS vs [FPTAS]) +- [APX]: there is an [approximation_algorithm] for a certain fixed epsilon Up: [complexity_class] of [approximation] 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,9 +3,11 @@ - [state] - [initial_state] - [final_state] + - [nonfinal_state] - [sink_state] - [transient_state] - [transition] + - [transition_function] - [alphabet] - [run] - [accepting_run] diff --git a/automata_constructions b/automata_constructions @@ -3,10 +3,11 @@ - [chrobak_normal_form] - [powerset_automata] for [automata_determinization] - [minimization_automaton] -- [automata_reversal], does not preserve [automata_determistic] +- [automata_reversal] + - does not preserve [automaton_determinism] - [automata_complementation] - [product_automaton], for [automaton_intersection] -- [automata_trimming] / [automata_completion] +- [automaton_trimming] / [automaton_completion] Up: [automata] diff --git a/automata_deterministic b/automata_deterministic @@ -1,8 +1,8 @@ # Automata deterministic [automata] where for each [state] and [letter] there is at most one outgoing [transition] -- possibly none for [automata_incomplete] +- possibly none for [incomplete_automata] Up: [automata_types], [determinism_language] -Aliases: automaton deterministic, deterministic automaton, deterministic automata, DFA, DFAs +Aliases: automaton deterministic, deterministic automaton, deterministic automata, DFA, DFAs, automaton determinism, automata determinism 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_reversal b/automata_reversal @@ -0,0 +1,7 @@ +# Automata reversal + +https://fr.wikipedia.org/wiki/Automate_transpos%C3%A9 + +Recognizes [language_mirror] + +Up: [automata_constructions] diff --git a/automata_types b/automata_types @@ -15,8 +15,8 @@ - [automata_alternating] - [automata_generalized] - [automata_trimmed] -- [automaton_complete] -- [automata_incomplete] +- [complete_automaton] +- [incomplete_automaton] ## Extensions 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_complete b/automaton_complete @@ -0,0 +1,11 @@ +# Automaton complete + +A [deterministic_automaton] where the [transition_function] is a [total_function], i.e., for every [state] q and [letter] a there is an outgoing [transition] for q and a + +Contrast with [incomplete_automata] where the [transition_function] is [partial] + +We can do [automaton_completion] to transform an [incomplete_automata] into a complete automaton + +Up: [automata_types] + +Aliases: complete automaton, complete automata diff --git a/automaton_completion b/automaton_completion @@ -0,0 +1,7 @@ +# Automaton completion + +The process of transforming an [incomplete_automaton] into a [complete_automaton] by adding a [sink_state] + +Up: [automata_constructions] + +See also: [automaton_trimming] diff --git a/automaton_epsilon_transitions b/automaton_epsilon_transitions @@ -0,0 +1,7 @@ +# Automaton epsilon transitions + +[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/automaton_trimming b/automaton_trimming @@ -0,0 +1,7 @@ +# Automaton trimming + +The process of transforming a [complete_automaton] into an [incomplete_automaton] by removing all [useless_states] + +Up: [automata_constructions] + +See also: [automaton_completion] 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/buchbinder2019simple b/buchbinder2019simple @@ -0,0 +1,5 @@ +# Buchbinder2019simple + +[approximation], [multiway_cut] + +Up: [academic_paper] on [multiway_cut] diff --git a/c2 b/c2 @@ -7,6 +7,8 @@ Does not enjoy [Craig_interpolation], according to [cate2023craig] Does not enjoy [finite_model_property] - but [satisfiability] is [decidable], cf [pratt2010two] +Turns out to be the expressive power of [Weisfeiler_Leman] + subclass: [gc2] Up: [logic] diff --git a/canonical_labeling b/canonical_labeling @@ -7,6 +7,8 @@ https://mathoverflow.net/a/11715 also called "graph canonization" -See also: [graph_isomorphism] +See also: [graph_isomorphism], [minimization_automaton] Up: [graph] + +Aliases: graph canonical labeling, graph canonization diff --git a/cartesian_product b/cartesian_product @@ -0,0 +1,8 @@ +# Cartesian product + +The *cartesian products* of two [sets] S and T is the [set] of [ordered_pairs] + - (s, t) with s in S and t in T + +Up: [mathematics] + +See also: [join_query], [Decomposability] 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/commutative_closure b/commutative_closure @@ -0,0 +1,9 @@ +# Commutative closure + +The *commutative closure* of a [formal_language] L is the set of all [words] that admit a [permutation] in L + +[commutative_closure_does_not_preserve_regularity]: If L is a [regular_language], then the commutative closure is not necessarily a [regular_language] + +Up: [formal_language_closure_operation] + +See also: [language_commutative] diff --git a/commutative_closure_does_not_preserve_regularity b/commutative_closure_does_not_preserve_regularity @@ -0,0 +1,5 @@ +# Commutative closure does not preserve regularity + +If L is a [regular_language], then the commutative closure is not necessarily a [regular_language]! + +Up: [mathematical_observation] about [commutative_closure] and [regular_languages] 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_normal_form b/conjunctive_normal_form @@ -9,6 +9,7 @@ Types: - [3cnf] - [kcnf] - [cnf_variable_convex] +- [hitting_cnf] lower bound on size of CNF relative to [disjunctive_normal_form] 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_acyclic b/conjunctive_query_acyclic @@ -6,12 +6,17 @@ Can be evaluated by [yannakakis_algorithm] following a [join_tree] the evaluation problem is in the complexity class [logcfl], and the the complexity is in O(database×query + output) -We can test in linear time if a hypergraph is acyclic and if so build the join tree: [gyo] algorithm +We can test in linear time if a [hypergraph] is acyclic and if so build the join tree: [gyo] algorithm +- not so obvious to understand where the [linear_time] claim comes from... For Boolean queries, even with [self_join], if the query is not acyclic then we can reduce from a hard problem ([triangle_detection] ou [hyperclique_detection]) Special case: [conjunctive_query_hierarchical] +Testing if a CQ is acyclic ([elimination_order]): + +- while there is a vertex v whose [closed_neighborhood] (includes v itself) is included in some edge, then delete the vertex + See also: [fagin1983degrees], [guarded_fragment], [alpha_acyclic], [conjunctive_query_cyclic] Up: [conjunctive_query] 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_full b/conjunctive_query_full @@ -4,4 +4,4 @@ A [CQ] without [projection]; also called a [join] query Up: [conjunctive_query], [query_full] -Aliases: full conjunctive query, full CQ, full CQs +Aliases: full conjunctive query, full CQ, full CQs, join query, join queries diff --git a/conjunctive_query_inequality b/conjunctive_query_inequality @@ -0,0 +1,11 @@ +# Conjunctive query inequality + +A [CQ] with [inequality_mathematics] + +- [union_of_conjunctive_query_inequality] + +Up: [conjunctive_query], [inequality_mathematics] + +See also: [query_with_negation] + +Aliases: CQ inequalities diff --git a/context_free_grammar b/context_free_grammar @@ -19,6 +19,8 @@ - [context_free_grammar_unambiguous] - [context_free_grammar_linear] - [context_free_grammar_bounded] +- [context_free_grammar_polyslender] +- [context_free_grammar_finite] - [inherently_ambiguous] ## Complexities diff --git a/context_free_grammar_bounded b/context_free_grammar_bounded @@ -1,6 +1,6 @@ # Bounded context-free grammar -[polynomial] [density_function] +[context_free_grammar] recognizing [language] which is [language_bounded] Up: [context_free_grammar] 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/context_free_grammar_unambiguous b/context_free_grammar_unambiguous @@ -7,3 +7,5 @@ An unambiguous CFG is a [context_free_grammar] where for every [word] in the lan Up: [unambiguity], [context_free_grammar] See also: [inherently_ambiguous] + +Aliases: unambiguous CFG, unambiguous CFGs diff --git a/context_free_language b/context_free_language @@ -3,7 +3,9 @@ [language] accepted by [context_free_grammar] - [context_free_language_membership] +- [context_free_language_slender] +- [context_free_language_polyslender] Up: [language], [context_free_grammar] -Aliases: context-free languages, context free languages, context-free language, CFL +Aliases: context-free languages, context free languages, context-free language, CFL, CFLs diff --git a/convexity b/convexity @@ -4,5 +4,6 @@ - [convex_set] - [convex_hull] - [cnf_variable_convex] +- [language_convex] Up: [mathematics] 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/dahlhaus1994complexity b/dahlhaus1994complexity @@ -0,0 +1,8 @@ +# Dahlhaus1994complexity + +[academic_paper] about [submodular_minimization] and [network_flow] + +- [network_flow_submodular] +- [multiway_cut] + +Up: [academic_paper] diff --git a/data_word b/data_word @@ -0,0 +1,10 @@ +# Data word + +like [word] but on an infinite or very large alphabet + +notions of [automaton]: +- symbolic automata, written with a [logical_formula] on transitions +- parametric automata: same but with a global parameter guesed at the beginning of the computation (existential) +- [register_automata] + +Up: [word] 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/degree b/degree @@ -8,3 +8,5 @@ In [directed_graphs], we can distinguish the [indegree] and [outdegree], respect - [average_degree] Up: [graph_basic_notions] + +See also: [bounded_degree] diff --git a/density_function b/density_function @@ -5,12 +5,17 @@ function defined on an [automata] and giving the number of words of a given leng possible regimes: exponential, polynomial, etc. - [language_slender] +- [language_polyslender] - [language_polynomially_bounded] [counting_problem] of evaluating it: [sharp_automaton] testing which lengths can be achieved, on [NFAs]: [potechin2020lengths] +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/derivative b/derivative @@ -0,0 +1,11 @@ +# Derivative + +https://en.wikipedia.org/wiki/Brzozowski_derivative + +Given a [word] u and a [formal_language] L, the *derivative* of L by u, written u^{-1} L, is the set of [words] v such that we have uv in L + +We can also define the *derivative* of a [formal_language], cf [quotient_formal_language] + +See also: [variety] + +Up: [formal_language] 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/disjunctive_normal_form_orthogonal b/disjunctive_normal_form_orthogonal @@ -1,14 +1,14 @@ # Disjunctive normal form orthogonal -[disjunctive_normal_form] where for any two "terms" they are not mutually satisfiable -(so it is an [unambiguous] [disjunctive_normal_form]) +[disjunctive_normal_form] where for any two [terms] they are not mutually satisfiable +- so it is an [unambiguous] [disjunctive_normal_form] -Could be called "unambiguous DNF" - -What is the complement called? it's a [conjunctive_normal_form] where the disjunction of any two clauses is tautological +[complement]: [hitting_cnf] note that necessarily the clauses (all except at most one) must be big (at least n/2) to satisfy this condition [disjunctive_normal_form_orthogonal_negation] Up: [disjunctive_normal_form] + +Aliases: unambiguous DNF, unambiguous DNFs 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/dsdnnf b/dsdnnf @@ -5,3 +5,5 @@ not closed under [complementation], cf [vinallsmeeth2024structured] by [harry] Up: [knowledge_compilation_classes], [ddnnf], [sdnnf] + +Aliases: dSDNNFs 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_push_pop b/dynamic_membership_push_pop @@ -0,0 +1,5 @@ +# Dynamic membership push pop + +- for [regular_languages]: [guardian_algorithm] in [ganardi2022low] + +Up: [dynamic_membership_word], [push_pop] 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,14 @@ +# Dynamic membership word + +- [dynamic_membership_regular] +- [incremental_maintenance_cfg] + +Depends on which [updates_word] are allowed: +- for [push_pop]: [dynamic_membership_push_pop] + +[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/enumeration b/enumeration @@ -8,6 +8,7 @@ https://en.wikipedia.org/wiki/Enumeration_algorithm - [enumeration_complexity] - [enumeration_related_work] - [enumeration_open_problems] +- [enumeration_algorithms] ## Related problems diff --git a/enumeration_delay b/enumeration_delay @@ -9,3 +9,5 @@ Possible types: - [polylog_delay] Up: [enumeration_definition] + +See also: [access_time] 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/equivalence_relation b/equivalence_relation @@ -4,4 +4,4 @@ A [mathematics_relation] is an equivalence relation if it is [relation_symmetric Up: [mathematics] -See also: [equivalence_class], [quotient] +See also: [equivalence_class], [quotient], [partition] 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,8 +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_property b/finite_model_property @@ -0,0 +1,11 @@ +# Finite model property + +A [logical_fragment] has the *finite model property* if whenever a [sentence] of this fragment has a [model] then it has a [finite_model] (of course the converse [implication] is obvious) + +Generalizations: + +- [finite_controllability] + +Up: [property] of [logical_fragment] + +Aliases: FMP diff --git a/finite_model_theory b/finite_model_theory @@ -2,4 +2,6 @@ - [finite_controllability] -Up: [logic], [finite] +Up: [model_theory], [finite] + +See also: [Open_world_query_answering] diff --git a/finite_simple_group b/finite_simple_group @@ -0,0 +1,9 @@ +# Finite simple group + +A finite [group] is simple if it does not have non-trivial [normal_subgroups] + +[classification_of_finite_simple_groups] + +Up: [group], [finite] + +Aliases: finite simple groups diff --git a/formal_language_closure_operation b/formal_language_closure_operation @@ -0,0 +1,11 @@ +# Formal language closure operation + +Specific case: [regular_language_closure_operation] + +- [upwards_closure] +- [downwards_closure] +- [commutative_closure] + +Up: [closure_operation], [formal_language] + +See also: [formal_language_operator] diff --git a/formal_language_mirror b/formal_language_mirror @@ -0,0 +1,9 @@ +# Formal language mirror + +The mirror of a [formal_language] L is the language formed of the [mirrors] of the [words] of L + +Up: [formal_language_operator] + +Aliases: language mirror, mirror language + +See also: [commutative_closure] diff --git a/formal_language_operator b/formal_language_operator @@ -0,0 +1,22 @@ +# Formal language operator + +An [operator] that takes one or two [formal_languages] and creates a new [formal_language] + +- [boolean_operators] + - [language_union] + - [language_intersection] + - [language_complementation] +- [concatenation] +- [kleene_star] +- [morphism] / [inverse_morphism] +- [quotient_formal_language] + - see [derivative] +- [wreath_product] +- [semidirect_product] +- [shuffle] +- [formal_language_mirror] +- [formal_language_closure_operation]: an operator that takes one [formal_language] and extends it by adding more [words] to it + - [upward_closure] / [downward_closure] + - [commutative_closure] + +Up: [formal_language], [operator] diff --git a/formal_series b/formal_series @@ -0,0 +1,5 @@ +# Formal series + +https://en.wikipedia.org/wiki/Formal_power_series + +Up: [mathematics] 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/gql b/gql @@ -0,0 +1,6 @@ +# GQL + +- [francis2023researchers]: explanation GQL +- [francis2023gpc] introduces [gpc] which is equivalent to GQL but easier to understand + +Up: [graph_query_languages_standards] 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_compressed_representation b/graph_compressed_representation @@ -0,0 +1,6 @@ +# Graph compressed representation + +- [graph_ring]: [arroyuelo2021worst], [arroyuelo2023optimizing] +- [k2_tree] + +Up: [graph_representation] 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/gray_code b/gray_code @@ -1,12 +1,16 @@ # Gray code - [mutze2022combinatorial]: [survey_paper] - - avoiding a given [subword], cf [squire1996gray] and references from above survey + - avoiding a given [subword] + - cf [squire1996gray] and references from [mutze2022combinatorial] - cf [minimal_absent_word] - older survey: [savage1997survey] - [shuffle_exchange_network] [feldmann1996shuffle] +construction: +- [reflected_binary_code] + Up: [enumeration] See also: [middle_levels_conjecture], [torsten] 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/group b/group @@ -0,0 +1,23 @@ +# Group + +A *group* is an [algebraic_structure] which is like a [monoid] but additionally requires that each [element] has an [inverse] + +Types of groups: + +- [coxeter_groups] +- [solvable_group] +- [group_abelian] + +[Theorems]: + +- classification of [finite_simple_groups] +- [feit_thompson] theorem + +Tools: + +- [cayley_graph] +- [cayley_table] + +Up: [algebraic_structure], [mathematics] + +See also: [monoid], [group_language] diff --git a/group_abelian b/group_abelian @@ -1,5 +1,9 @@ # Group abelian -[commutative] +A [group] which is [commutative] -Up: [group] +Up: [group], [commutative] + +Aliases: abelian group, abelian groups + +See also: [language_commutative], [semiring_commutative] diff --git a/gt_maj_sat b/gt_maj_sat @@ -0,0 +1,11 @@ +# GT-MAJ-SAT + +given a [boolean_formula] in [conjunctive_normal_form], determine if >1/2 of the [valuations] are satisfying + +- [akmal2021majority]: + - it is [np_complete] for k geq 4 + - and in [ptime] for k leq 3 +- [tantau2022satisfaction]: + - classification for fixed threshold delta and value k of the [clause_width] + +Up: [maj_sat] diff --git a/guardian_algorithm b/guardian_algorithm @@ -0,0 +1,7 @@ +# Guardian algorithm + +https://cstheory.stackexchange.com/questions/45890/constraints-on-sliding-windows/46762 + +[ganardi2022low] + +Up: [algorithm] for [dynamic_membership_push_pop] diff --git a/hitting_cnf b/hitting_cnf @@ -0,0 +1,9 @@ +# Hitting cnf + +A [conjunctive_normal_form] where the [disjunction] of any two [clauses] is [tautological] + +[Negation]: [disjunctive_normal_form_orthogonal] + +Up: [conjunctive_normal_form] + +See also: [hitting_set] diff --git a/homomorphism b/homomorphism @@ -13,3 +13,5 @@ Variants: Up: [mathematics] See also: [core] + +Aliases: homomorphisms 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/hypergraph b/hypergraph @@ -7,6 +7,7 @@ generalizes [graph] - [vertex] - [hyperedge] - [primal_graph] aka "Gaifman graph" +- [subhypergraph] ## Classes diff --git a/incomplete_automaton b/incomplete_automaton @@ -0,0 +1,9 @@ +# Incomplete automaton + +A [DFA] where the [transition_function] is a [partial_function] + +Up: [automata_types] + +See also: [partial_automaton], [automaton_complete] + +Aliases: incomplete automata 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/inequality_mathematics b/inequality_mathematics @@ -0,0 +1,10 @@ +# Inequality (mathematics) + +- [conjunctive_query_inequality] +- [enumeration_inequality] + +See also: [concentration_inequality], [partial_order], [inequation], [disequality], [equality] + +Up: [mathematics] + +Aliases: mathematics inequality, mathematics inequalities 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_commutative b/language_commutative @@ -0,0 +1,9 @@ +# Commutative language + +- [regular_language_commutative] + +Up: [formal_language] which is [commutative] + +See also: [parikh_image], [Commutative_closure] + +Aliases: commutative language, commutative languages diff --git a/language_complementation b/language_complementation @@ -0,0 +1,7 @@ +# Language complementation + +The [complementation] of a [formal_language] + +Up: [complementation] + +Aliases: language complement diff --git a/language_downwards_closed b/language_downwards_closed @@ -0,0 +1,20 @@ +# Language downwards closed + +A [formal_language] is *downwards closed* if any [subword] of the [formal_language] is in the [formal_language] + +[ideal_decomposition]: every downward closed language is a finite [union] of [language_ideal] i.e. terms of the form + + A_1^* {a_1, epsilon} ... A_k^* + where the A_i are subalphabets + +[language_downwards_closed_details] + +The [language_complement] of a downwards closed [formal_language] is a [upwards_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], [downwards_closure], [language_factor_minimal], [language_upwards_closed], [ganardi2024directed] + +Aliases: downward closed language, downward closed languages, downwards closed language, downwards closed languages 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/lmim_width b/lmim_width @@ -0,0 +1,9 @@ +# LMIM width + +This is to [mim_width] like [pathwidth] is to [treewidth] + +cf [golovach2017output] + +Can be computed on [trees] in [log_linear] time, cf [hogemo2019linear] + +Up: [mim_width], [width_measure_linear] 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 @@ -49,11 +51,12 @@ - [craig_interpolation] - [ehrenfeucht_fraisse_game] - [fo_interpretation] -- [quantifier_rank] -- [conjunction] -- [disjunction] -- [implication] +- [boolean_connective] + - [conjunction] + - [disjunction] + - [implication] - [variable] + - [free_variable] - [negation] - [zero_one_law] - [craig_interpolation] @@ -62,7 +65,10 @@ - [monadic] - [logic_formula] - [quantifier] + - [quantifier_rank] - [logical_implication] +- [sentence] +- [function_symbol] Up: [mathematics], [theoretical_computer_science] diff --git a/lower_bounds b/lower_bounds @@ -1,14 +1,10 @@ # Lower bounds -Class at [mit] http://courses.csail.mit.edu/6.5440/fall23/ - -videos and well-down course notes https://courses.csail.mit.edu/6.892/spring19/lectures/ - -Work in progress [book] "Computational Intractability: A Guide to Algorithmic Lower Bounds" https://hardness.mit.edu/ -- not intended to be [open_access] apparently +- [complexity_lower_bounds] +- [conditional_lower_bound] Up: [computational_complexity] -See also: [theorem] +See also: [theorem], [upper_bound] Aliases: lower bound diff --git a/mathematics b/mathematics @@ -2,40 +2,7 @@ ## Basic concepts -- [set] - - [semilinear_set] -- [partition] - - [equivalence_relation] -- [order] - - [partial_order] - - [inequality_mathematics] -- [algebraic_structure] - - [monoid] - - [semigroup] - - [group] - - [semiring] - - [ring] - - [field] - - [homomorphism] -- [distance] -- [vector] -- [number] -- [formal_series] -- [polynomial] -- [lattice] -- [logarithm] -- [matrix] -- [function] -- [equation] - - [equation_system] - - [inequation] - - [disequation] -- [sequence] -- [cartesian_product] -- [plane_mathematics] -- [modulo] -- [relation_mathematics] -- [integer] +[mathematics_basic_concepts] ## Notions @@ -54,6 +21,7 @@ - [disequality] - [symmetry] - [composition] +- [number] ## Fields diff --git a/mathematics_basic_concepts b/mathematics_basic_concepts @@ -0,0 +1,41 @@ +# Mathematics basic concepts + +- [set] + - [semilinear_set] +- [partition] + - [equivalence_relation] +- [order] + - [partial_order] + - [inequality_mathematics] + - [minimum] / [maximum] +- [algebraic_structure] + - [monoid] + - [semigroup] + - [group] + - [semiring] + - [ring] + - [field] + - [homomorphism] +- [sum], [product] +- [distance] +- [vector] +- [number] +- [formal_series] +- [polynomial] +- [lattice] +- [logarithm] +- [matrix] +- [function] +- [equation] + - [equation_system] + - [inequation] + - [disequation] +- [sequence] +- [cartesian_product] +- [plane_mathematics] +- [modulo] +- [relation_mathematics] +- [integer] +- [fraction] + +Up: [mathematics] 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 @@ -0,0 +1,17 @@ +# Matrix multiplication + +In specific [semirings]: +- [matrix_multiplication_boolean] + - [combinatorial_boolean_matrix_multiplication] +- [min_plus_matrix_multiplication] + +- [matrix_multiplication_algorithms] +- [matrix_multiplication_exponent] omega + - open question of what is the best exponent + - [omm_conjecture] + +Up: [multiplication] of [matrix] + +See also: [algorithm], [matrix_product] + +Aliases: matrix product diff --git a/matrix_multiplication_algorithms b/matrix_multiplication_algorithms @@ -0,0 +1,6 @@ +# Matrix multiplication algorithms + +- [strassens_algorithm] +- [karatsuba_algorithm] + +Up: [algorithms] for [matrix_multiplication] diff --git a/maximum b/maximum @@ -0,0 +1,10 @@ +# Maximum + +the largest [element] of an [order] +- [supremum] + +See also: [minimum], [maximization_problem] + +Up: [mathematics_basic_concepts] + +Aliases: max diff --git a/maximum_linear_arrangement b/maximum_linear_arrangement @@ -0,0 +1,7 @@ +# Maximum linear arrangement + +cf [alemanypuig2024maximum] + +See also: [minimum_linear_arrangement] + +Up: [computational_problem] on [graph] diff --git a/mim_width b/mim_width @@ -4,7 +4,7 @@ defined in [vatshelle2012new] via [induced_matching] -linear version [lmim_width], like [pathwidth] is to [treewidth], cf [golovach2017output] +[width_measure_linear]: [lmim_width] variant [sim_width] 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/minimization b/minimization @@ -5,3 +5,7 @@ - [automaton_minimal] Up: [theoretical_computer_science] + +Aliases: minimized + +See also: [minimum], [maximization] diff --git a/minimization_automaton b/minimization_automaton @@ -7,4 +7,6 @@ Up: [minimization] -Aliases: minimization of automata, automata minimization, automaton minimization, minimization automata +Aliases: minimization of automata, automata minimization, automaton minimization, minimization automata, automaton minimal, minimal automaton + +See also: [canonical_labeling] diff --git a/minimum b/minimum @@ -0,0 +1,12 @@ +# Minimum + +The smallest element of an [order] +- may not exist if it is [infinite] + - [infimum] +- may not be unique if the [order] is not [total_order] + +Up: [mathematics_basic_concepts] + +See also: [maximum], [minimization] + +Aliases: min diff --git a/minimum_length_bounded_multicut b/minimum_length_bounded_multicut @@ -0,0 +1,6 @@ +# Minimum length bounded multicut + +- studied in practical terms in [kuhnle2018network] +- studied in [parameterized_complexity] by [dvorak2018parameterised] + +Up: [minimum_multicut], [minimum_cut_length_bounded] diff --git a/minimum_linear_arrangement b/minimum_linear_arrangement @@ -0,0 +1,11 @@ +# Minimum linear arrangement + +Given a [graph], find a [permutation] of the [vertices] such that the [sum] across [edges] of the difference between the permutation image of the two endpoint [vertices] is [minimized] + +The problem is [NP_complete] + +cf [bienkowski2024improved] + +Up: [computational_problem] on [graph] + +See also: [graph_layout], [maximum_linear_arrangement] diff --git a/minimum_multicut b/minimum_multicut @@ -0,0 +1,14 @@ +# Minimum multicut + +[costa2005minimal] + +Also [minimum_length_bounded_multicut] + +Special case: [bicut]: separate s from t and t from s in [graph_directed] +- already [NP_hard] + +Lots of [approximation] results, e.g., [chitnis2019fpt] +- also on [directed_acyclic_graph]: + - [kratsch2015fixed]; also talks about [skew_multicut] + +Up: [minimum_cut] diff --git a/mirror b/mirror @@ -0,0 +1,9 @@ +# Mirror + +Given a [word] w = a_1 ... a_n, its mirror is w' = a_n ... a_1 + +Up: [word] + +See also: [automata_reversal], [palindrome], [commutative_closure] + +Aliases: mirrors diff --git a/modular_decomposition b/modular_decomposition @@ -0,0 +1,5 @@ +# Modular decomposition + +https://en.wikipedia.org/wiki/Modular_decomposition + +Up: [width_measure], [graph_decomposition] diff --git a/modulo b/modulo @@ -0,0 +1,9 @@ +# Modulo + +- [modular_arithmetic] +- [parity] +- [edge_minimum_walk_modulo] + +Up: [mathematics] + +See also: [equivalence_relation], [modular_decomposition], [modular_function] diff --git a/monoid b/monoid @@ -0,0 +1,19 @@ +# Monoid + +A [semigroup] with [neutral_element] + +## In [semiring_provenance] + +- [monoid_ordered] with [natural_order] +- [monoid_positive] + +## In [formal_language_theory] + +- [syntactic_monoid] +- [monoid_aperiodic] +- [transition_monoid] +- [monoid_definite] + +Up: [algebraic_structure], [mathematics] + +See also: [group], [semigroup], [monoid_law] 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/multiway_cut b/multiway_cut @@ -0,0 +1,20 @@ +# Multiway cut + +Given [undirected_graph] G with edge weights, and set of terminals T, compute a minimum-weight subset of [edges] such that all terminals are disconnected when removing these edges + +[NP_hard] already for k=3 [dahlhaus1994complexity], already on unweighted [undirected_graphs] +- reduction from [simple_max_cut] + +[academic_papers] on [approximation]: [buchbinder2019simple] + +- lots of works on various [graph_classes], e.g., [pandey2022planar] + - aka [multiterminal_cut] +- [garg1994multiway] + +Also on [directed_graphs]: [multiway_cut_directed] + +Up: [minimum_cut] + +See also: [minimum_multicut], [skew_multicut] + +Aliases: multiterminal cut 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 @@ -0,0 +1,12 @@ +# Negation + +- [negation_semantics] +- [stratification] +- [guarded_negation] +- [datalog_negation] +- [negation_as_failure] +- [first_order_logic_existential_positive] + +Up: [logic] + +Aliases: negated, negations diff --git a/network_flow_submodular b/network_flow_submodular @@ -0,0 +1,7 @@ +# Network flow submodular + +connections between [network_flow] and [submodular_minimization] + +- [dahlhaus1994complexity] Section 4.1 + +Up: [network_flow], [submodular_minimization] 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/normal_subgroup b/normal_subgroup @@ -9,3 +9,5 @@ Can be used to build [quotient_group] by a [congruence_relation]: the equivalenc When the group is [abelian_group], all subgroups are normal Up: [finite_simple_group] + +Aliases: normal subgroups diff --git a/npmv b/npmv @@ -0,0 +1,5 @@ +# NPMV + +https://complexityzoo.net/Complexity_Zoo:N#npmv + +Up: [complexity_class] diff --git a/nptime b/nptime @@ -15,3 +15,5 @@ subset [up] Up: [complexity_class] See also: [ptime], [np_complete], [np_hard], [np_cap_conp], [conp], [nondeterministic_PTIME_Turing_machine] + +Aliases: NP 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/order b/order @@ -5,5 +5,6 @@ - [inequality_mathematics] - [linear_extension], see also [topological_sort] - [well_quasi_ordering] +- [upper_bound] / [lower_bound] Up: [mathematics] diff --git a/packing_coloring b/packing_coloring @@ -0,0 +1,9 @@ +# Packing coloring + +work with [bernardo] + +https://www.quantamagazine.org/the-number-15-describes-the-secret-limit-of-an-infinite-grid-20230420/ + +Up: [mathematics] + +See also: [graph_coloring], [packing_problem] diff --git a/palindrome b/palindrome @@ -5,3 +5,5 @@ Up: [word] See also: [manachers_algorithm], [context_free_language] + +Aliases: palindromes diff --git a/parikh_image b/parikh_image @@ -0,0 +1,16 @@ +# Parikh image + +The *Parikh image* of a [word] is the [vector] of the number of occurrences of the letters that it contains, and the *Parikh image* of a [formal_language] is the set of Parikh images of the [words] that it contains + +[Parikhs_theorem]: the Parikh images of [CFLs] and of [regular_languages] are the same! + +The Parikh image is not always [recognizable] even for a [regular_language] +- https://cstheory.stackexchange.com/questions/46670/languages-whose-parikh-image-is-recognizable +- it relates to [regular_languages] whose [commutative_closure] is also a [regular_language] + - cf [commutative_closure_does_not_preserve_regularity] + +Up: [formal_language_theory] + +See also: [language_commutative], [length] + +Aliases: parikh images 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_order b/partial_order @@ -0,0 +1,27 @@ +# Partial order + +Variants: +- [strict]: [irreflexive], [asymmetric], [relation_transitive] +- non-strict: [reflexive], [relation_transitive], [antisymmetric] + +- [poset_rank] +- [partial_order_dimension] + - connections to [treewidth] +- [crown] and link with [partial_order_dimension] + - [trotter1973dimension] +- [order_type] + +- [omega_complete] +- [ascending_chain_condition] + - generalization [poset_rank]: largest rank of a stricly increasing [chain] + - (minus one: x0 < ... < xr has rank r) + +- [least_upper_bound] +- [greatest_lower_bound] + +- [dilworths_theorem] for [chain_partitioning] +- [poset_width]: largest [antichain] cardinality + +Up: [mathematics], [order] + +See also: [preorder], [monotone] 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/partition b/partition @@ -1,5 +0,0 @@ -# Partition - -Up: [mathematics] - -See also: [laminar_set_family], [partition_problem], [equivalence_relation] diff --git a/pathwidth b/pathwidth @@ -3,7 +3,8 @@ like [treewidth] but for [tree_decomposition] which is a [path] - [pathwidth_directed] -- [pathwidth_approximation] +- [pathwidth_computation] + - [pathwidth_approximation] Up: [width_measure], [path] diff --git a/pathwidth_computation b/pathwidth_computation @@ -0,0 +1,12 @@ +# Pathwidth computation + +The [computational_problem] of computing the [pathwidth] of an input [graph] + +https://en.wikipedia.org/wiki/Pathwidth#Special_classes_of_graphs +- Is [NP_complete] even on [bounded_degree] [planar_graphs] +- Can be computed in [linear_time] for [trees] and [forests] +- Can be computed in [polynomial_time] for [treelike] [graphs] + +- [pathwidth_approximation] + +Up: [computational_problem], [pathwidth] 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/plane_mathematics b/plane_mathematics @@ -0,0 +1,7 @@ +# Plane (mathematics) + +a [vector_space] of [dimension] 2 + +Up: [mathematics] + +See also: [complex_plane] diff --git a/polynomial b/polynomial @@ -0,0 +1,23 @@ +# Polynomial + +- [polynomial_equation] +- [lagrange_interpolation] + +Types: + +- [polynomial_homogeneous] +- [polynomial_multivariate] + - [polynomial_multilinear] +- [polynomial_irreducible] +- [polynomial_factored] +- [polynomial_expanded] + +Concepts: + +- [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/pop_operation b/pop_operation @@ -0,0 +1,9 @@ +# Pop operation + +Given a non-empty [word] w and a side (left or right), remove the endpoint [letter] + +See also: [push_operation] + +Aliases: pop operations + +Up: [deletion] 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 @@ -12,3 +12,5 @@ When the input consists of integers, we distinguish: https://en.wikipedia.org/wi Up: [complexity_class] See also: [pseudo_polynomial_time], [quasipolynomial], [oplusp], [ptime_reduction] + +Aliases: P, polynomial time diff --git a/push_operation b/push_operation @@ -0,0 +1,9 @@ +# Push operation + +Given a [word] w and a [letter] a and one side of the word (left or right), add a to that side of the word + +Up: [insertion] + +See also: [pop_operation] + +Aliases: push operations diff --git a/push_pop b/push_pop @@ -0,0 +1,9 @@ +# Push pop + +The kinds of [updates_word] where you can do [push_operations] and [pop_operations] + +- [dynamic_membership_push_pop] + +For [dynamic_membership] + +Up: [update_word] 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/q9 b/q9 @@ -0,0 +1,7 @@ +# Q9 + +A specific [UCQ] used in [PQE] and in [jha2013knowledge] + +Up: [UCQ] + +See also: [monet2020solving] 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 b/query @@ -5,6 +5,7 @@ - [query_full] - [query_boolean] - [query_non_boolean] +- [query_with_negation] ## Problems diff --git a/query_boolean b/query_boolean @@ -4,8 +4,10 @@ A [query] whose [query_answer] is a [Boolean]: either the query holds or it does For [queries] with [free_variables] that are [first_order], the [computational_complexity] of computing [query_answers] is often [PTIME]-equivalent to the Boolean queries obtained by considering each of the polynomially many possible answers and creating a Boolean query by insantianing these [variables] to [constants] +In [logic], this is called a [sentence] + Up: [query] Aliases: boolean query -See also: [free_variable], [query_non_boolean] +See also: [free_variable], [query_non_boolean], [sentence] diff --git a/query_evaluation b/query_evaluation @@ -16,6 +16,8 @@ - [query_evaluation_incremental] +- [approximate_query_evaluation] + Up: [database_theory] See also: [query_language], [enumeration_query_answers] diff --git a/query_language b/query_language @@ -3,7 +3,7 @@ - [conjunctive_query] - [sjfcq] - [union_of_conjunctive_queries] -- [first_order_logic] +- [first_order_logic]: [first_order_query] - [monadic_second_order_logic] ## Other formalisms 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/random_graph b/random_graph @@ -4,4 +4,6 @@ also: [random_dfa] Up: [graph], [randomness] -See also: [random_walk] +See also: [random_walk], [random_hypergraph] + +Aliases: random graphs, graph random diff --git a/randomness b/randomness @@ -9,6 +9,7 @@ ## [random_structure] - [random_graph] +- [random_hypergraph] - [random_walk] - [random_dfa] 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/sampling b/sampling @@ -0,0 +1,16 @@ +# Sampling + +- [cardinality_estimation] +- [uniform_sampling] +- [sampling_query_answers] + - [sampling_cqs] +- [sampling_approximate] +- [monte_carlo] +- [coupon_collector_problem] +- [german_tank_problem] +- [square_root_biaised_sampling] +- [sampling_subgraph] + +Up: [algorithms] + +See also: [approximation] diff --git a/sampling_subgraph b/sampling_subgraph @@ -0,0 +1,7 @@ +# Sampling subgraph + +given a [graph] G and [subgraph] H, the [computational_problem] of [uniform_sampling] of an occurrence of H in G + +[wang2024sampling] + +Up: [computational_problem], [sampling], [subgraph] diff --git a/satisfiability_weighted b/satisfiability_weighted @@ -1,9 +0,0 @@ -# Weighted satisfiability - -[creignou2012satisfiability]: given a [Boolean_formula] phi and [integer] k, decide if phi has a [satisfying_assignment] of [hamming_weight] exactly k - -- [satisfiability_weighted_monotone_cnf] - -Up: [sat_variants] - -See also: [maxsat] diff --git a/sdnnf b/sdnnf @@ -1,5 +1,7 @@ # SDNNF -like [dnnf] but obeys [structuredness] +like [DNNFs] but [structured] Up: [knowledge_compilation_classes], [dnnf], [structuredness] + +Aliases: SDNNFs 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/semigroup b/semigroup @@ -0,0 +1,14 @@ +# Semigroup + +A [set] with a [semigroup_law] which is [associative] + +Special cases: + +- [monoid] +- [group] + +Examples: + +- [syntactic_semigroup] + +Up: [mathematics_basic_concepts] 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/shuffle b/shuffle @@ -1,6 +1,9 @@ # Shuffle +A [word] w is a *shuffle* of two [words] u and v if we can interleave the characters of u and v to form w. We can also define the *shuffle* of two [formal_languages] L and L' as the set of [words] w that are shuffles of a [word] of L and a [word] of L' + - [shuffle_square] -- a finite set of [word] can be decomposed into at most one multiset of which it is the shuffle: see [berstel2002shuffle] +- a finite set of [words] can be decomposed into at most one multiset of which it is the shuffle: + - see [berstel2002shuffle] -Up: [formal_language_theory] +Up: [formal_language_operator] diff --git a/simple_max_cut b/simple_max_cut @@ -0,0 +1,9 @@ +# Simple max cut + +in [dahlhaus1994complexity]: given an [undirected_graph] and an [integer] K, find a partition of the [vertices] in two [sets] V1 and V2 such that there are at least K [edges] between V1 and V2 + +[NP_complete] [computational_problem] + +See also: [multiway_cut], [cut] + +Up: [computational_problem] on [graph] 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/sparse_boolean_matrix_multiplication b/sparse_boolean_matrix_multiplication @@ -0,0 +1,10 @@ +# Sparse BMM + +[computational_hypothesis] : [boolean_matrix_multiplication] cannot be +performed in [linear_time] in the number of 1 entries + +Also: [fully_sparse_boolean_matrix_multiplication] + +Up: [fine_grained_complexity] + +See also: [boolean_matrix_multiplication], [sparse] diff --git a/square_root_biaised_sampling b/square_root_biaised_sampling @@ -0,0 +1,7 @@ +# Square root biaised sampling + +https://en.m.wikipedia.org/wiki/Square_root_biased_sampling + +sampling to find dangerous individuals using the [square_root] of [priors] + +Up: [sampling] 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/stratification b/stratification @@ -0,0 +1,7 @@ +# Stratification + +Useful for [datalog_aggregation] or [datalog_negation] + +Up: [datalog] + +See also: [Datalog_stratified] diff --git a/strong_exponential_time_hypothesis b/strong_exponential_time_hypothesis @@ -2,6 +2,8 @@ In the vocabulary of [exponential_time_hypothesis] it claims that lim_k s_k = 1 +[SETH_fine_grained] + Up: [exponential_time_hypothesis] Aliases: SETH 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/submodular_maximization b/submodular_maximization @@ -1,8 +1,8 @@ # Submodular maximization -[np_hard] +An [NP_hard] [computational_problem] -[buchbinder2024deterministic] +cf [buchbinder2024deterministic] Up: [submodular_optimization], [maximization] 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/syntactic_semigroup b/syntactic_semigroup @@ -0,0 +1,12 @@ +# Syntactic semigroup + +Two definitions: + +- The [semigroup] [spanned] by the [transition_functions] for the various [letters] of the [minimal_automaton] +- [quotient] of [words] by [syntactic_equivalence] + +A [formal_language] is [regular_language] iff syntactic semigroup is finite + +See also: [syntactic_monoid], [non_erasing_morphism], [stable_semigroup] + +Up: [semigroup] 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/ternary_goldbach_problem b/ternary_goldbach_problem @@ -0,0 +1,7 @@ +# Ternary goldbach problem + +https://en.wikipedia.org/wiki/Goldbach%27s_weak_conjecture + +See also: [goldbach_conjecture] + +Up: [number_theory] 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/transition b/transition @@ -7,3 +7,5 @@ A transition in an [automaton] goes from a [state] to another and is labeled by Up: [automata_concepts] Aliases: transitions + +See also: [transition_function] diff --git a/transition_monoid b/transition_monoid @@ -0,0 +1,8 @@ +# Transition monoid + +A [monoid] describing the effect of the various [letters] / [words] + - including the [empty_word] + +Can be seen as [adjacency_matrix], with [monoid_law] being [matrix_multiplication] + +Up: [monoid], [automata] 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/tree_decomposition b/tree_decomposition @@ -7,3 +7,5 @@ See also: [treewidth] Up: [tree] + +Aliases: tree decompositions diff --git a/triangle_detection b/triangle_detection @@ -0,0 +1,15 @@ +# Triangle detection + +https://en.wikipedia.org/wiki/Triangle-free_graph#Triangle_finding_problem + +[Computational_problem] of finding a [triangle] in an [undirected_graph] + +[computational_complexity]: +- For [dense_graphs], the best known [algorithm] is via [boolean_matrix_multiplication] and takes O(n^omega) for n vertices (and for an input of size Theta(n^2)) + - [itai1977finding] +- For [sparse_graphs], it is possible to do Otilde(m^{2omega/(omega+1)}) [alon1997finding] +- [triangle_detection_conjecture] + +Up: [computational_problem] on [graph], [conjunctive_query], [fine_grained_complexity_problems] + +See also: [all_edge_triangle], [boolean_matrix_multiplication], [sparse_triangle] 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/uniform_sampling b/uniform_sampling @@ -0,0 +1,7 @@ +# Uniform sampling + +[sampling] from [uniform_distribution] + +[FPAUS]: fully-polynomial almost uniform sampler + +Up: [sampling] 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 @@ -10,3 +10,7 @@ - [word_split]: related to [cut_and_paste] Up: [update] for [word] + +See also: [dynamic_word], [edit_distance_operations] + +Aliases: updates word diff --git a/upwards_closure b/upwards_closure @@ -0,0 +1,16 @@ +# Upwards closure + +For L a [formal_language], the *upwards closure* of L is the set of [words] w which are [supersequences] of a word of L + +For any [formal_language] L, the upwards closure is a [regular_language]: this uses [Higman's_lemma] + +The upwards closure is a [upwards_closed_language]: any [supersequence] of a [word] of the upwards closure is in the upwards closure + +- [upwards_closure_state_complexity] + - [upwards_closure_cfl_state_complexity] + +See also: [language_upwards_closed], [downwards_closure] + +Up: [formal_language_operator], [closure_operation] on [supersequences] + +Aliases: upward closure, superword closure 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/width_measure_linear b/width_measure_linear @@ -0,0 +1,6 @@ +# Width measure linear + +- [pathwidth] +- [lmim_width] + +Up: [width_measure] 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