commit 6db52342590b12e32f3981d7cd7e6a8f836b318a parent 3ed32d94379637adf786c9c0bc0d309e3616cb34 Author: Antoine Amarilli <a3nm@a3nm.net> Date: Tue, 4 Feb 2025 12:00:55 +0100 commit with codex Diffstat:
46 files changed, 423 insertions(+), 7 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/automata_concepts b/automata_concepts @@ -6,6 +6,7 @@ - [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_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/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,5 @@ +# Automaton epsilon transitions + +[automata_nondeterministic] with [epsilon_transition] + +Up: [automata_types] 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/buchbinder2019simple b/buchbinder2019simple @@ -0,0 +1,5 @@ +# Buchbinder2019simple + +[approximation], [multiway_cut] + +Up: [academic_paper] on [multiway_cut] 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/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/formal_series b/formal_series @@ -0,0 +1,5 @@ +# Formal series + +https://en.wikipedia.org/wiki/Formal_power_series + +Up: [mathematics] 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_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/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/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/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/mathematics_basic_concepts b/mathematics_basic_concepts @@ -0,0 +1,40 @@ +# 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] +- [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_multiplication b/matrix_multiplication @@ -0,0 +1,15 @@ +# 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] 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,8 @@ +# Maximum + +the largest [element] of an [order] +- [supremum] + +See also: [minimum] + +Up: [mathematics_basic_concepts] diff --git a/minimization_automaton b/minimization_automaton @@ -7,6 +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,10 @@ +# 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] 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_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/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/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/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/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/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,10 @@ +# Polynomial + +- [polynomial_equation] +- [lagrange_interpolation] + +Up: [mathematics] + +See also: [polynomial_irreducible] + +Aliases: polynomials 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/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/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/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/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/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/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/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/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]