commit 1461165678175433b9689f151a39de534df16199 parent 6ff738f3e298054e38a71786d30c394f4ba2903a Author: Antoine Amarilli <a3nm@a3nm.net> Date: Fri, 13 Jun 2025 12:03:31 +0200 commit with codex Diffstat:
36 files changed, 264 insertions(+), 1 deletion(-)
diff --git a/automata_determinization b/automata_determinization @@ -13,4 +13,4 @@ Bounds for specific [automata_classes]: Up: [automata_constructions] -Aliases: automata determinized, determinization +Aliases: automata determinized, determinization, automaton determinize, automata determinize, automaton determinized, determinized diff --git a/backurs2016which b/backurs2016which @@ -5,3 +5,5 @@ uses [strong_exponential_time_hypothesis] and [orthogonal_vectors] [follow_up]: [bringmann2016dichotomy] Up: [academic_paper] on [regular_expression_matching] + +See also: [Ov_to_regular_expression_matching] diff --git a/buchis_theorem b/buchis_theorem @@ -5,3 +5,5 @@ https://en.wikipedia.org/wiki/B%C3%BCchi-Elgot-Trakhtenbrot_theorem Equivalence of [monadic_second_order_logic] and of [regular_languages] on [words] Up: [theorem] in [formal_language_theory] + +See also: [Büchi_automaton] diff --git a/bunkbed_conjecture b/bunkbed_conjecture @@ -0,0 +1,7 @@ +# Bunkbed conjecture + +refuted: [gladkov2024bunkbed] + +https://www.quantamagazine.org/maths-bunkbed-conjecture-has-been-debunked-20241101/ + +Up: [conjecture] diff --git a/cardinality_estimation_pessimistic b/cardinality_estimation_pessimistic @@ -0,0 +1,5 @@ +# Cardinality estimation pessimistic + +[cardinality_estimation] with theoretically guaranteed [upper_bounds], in connection with [optimal_joins] [abokhamis2024pessimistic] + +Up: [cardinality_estimation] diff --git a/connected_component b/connected_component @@ -7,3 +7,5 @@ An [equivalence_class] of the [reachability] [equivalence_relation] in an [undir See also: [strongly_connected_component], [graph_connected] Up: [graph_basic_notions] + +Aliases: connected components diff --git a/constant_weight_code b/constant_weight_code @@ -0,0 +1,7 @@ +# Constant weight code + +https://en.wikipedia.org/wiki/Constant-weight_code + +construction: [mambou2017construction] + +Up: [error_detection_and_correction_code] diff --git a/cubing b/cubing @@ -0,0 +1,7 @@ +# Cubing + +Putting at [exponent] 3 + +Up: [exponentiation] + +Aliases: cubes diff --git a/dnnf b/dnnf @@ -0,0 +1,21 @@ +# DNNF + +[decomposable] [negation_normal_form] + +Open: whether [sharp_dnnf] admits an [fpras] +- [FPRAS] claimed: [meel2024fpras] + +Special cases: +- [ordered_dnnf], cf [context_free_grammar] +- [sdd] +- [decision_dnnf] + - special case [ordered_decision_circuit] +- [disjunctive_normal_form] + +Compilation of DNNFs to [conjunctive_normal_form] cannot be done tractably because DNNFs include [DNFs] + +See also: [ddnnf], [decision_dnnf] + +Up: [knowledge_compilation_classes] + +Aliases: DNNFs diff --git a/enumeration_problem b/enumeration_problem @@ -0,0 +1,7 @@ +# Enumeration problem + +A [function_problem] where the output to compute is separated into results, and you can talk about the [delay] between any two results + +Up: [function_problem], [enumeration] + +Aliases: enumeration problems diff --git a/fo_mod b/fo_mod @@ -0,0 +1,11 @@ +# FO+MOD + +[first_order_logic] with [modularity_quantifier] + +[heimberg2016hanf]: [hanf_normal_form] for FQ+MOD + +[berkholz2017answering2]: [enumeration] for this class + +Up: [first_order_logic] with [modularity_quantifier] + +See also: [logic_counting], [straubing] diff --git a/formal_language_separation b/formal_language_separation @@ -0,0 +1,13 @@ +# Formal language separation + +Given two [formal_languages] L1 and L2 that are disjoint in a class C +a [formal_language] L in class C' separates them if L1 subseteq L and L cap L2 is empty + +[Formal_language_separation_problem] + +generalization to multiple languages: [formal_language_covering] +- cf [place2018covering] + +See also: [barcelo2023separating] + +Up: [formal_language_theory] diff --git a/function_problem b/function_problem @@ -0,0 +1,18 @@ +# Function problem + +A [computational_problem] where you must compute an [output] + +[Complexity_classes]: + +- [FP] +- [FNP] + +Examples: + +- [Query_evaluation] for [non_Boolean_queries] + +Specialization: [enumeration_problem] + +Up: [computational_problem] + +See also: [function] diff --git a/gapped_string_indexing b/gapped_string_indexing @@ -0,0 +1,7 @@ +# Gapped string indexing + +cf [amir2016gap] for instance + +See also: [subsequence_testing_gap_constraints] + +Up: [gap_constraints], [indexing] diff --git a/graph_traversal b/graph_traversal @@ -6,3 +6,5 @@ Up: [graph] See also: [shortest_path_algorithm] + +Aliases: graph traversals diff --git a/inclusion_dependency b/inclusion_dependency @@ -0,0 +1,5 @@ +# Inclusion dependency + +- [inclusion_dependency_unary] + +Up: [tuple_generating_dependency_linear] diff --git a/karmakar2024expected b/karmakar2024expected @@ -0,0 +1,5 @@ +# Karmakar2024expected + +by [senellart] and [mikael] + +Up: [academic_paper] about [shapley_value_expected] diff --git a/kcnf b/kcnf @@ -0,0 +1,10 @@ +# k-CNF + +A [conjunctive_normal_form] [boolean_formula] where every [clause] contains k [literals] (or "at most k" = [clause_width] bounded by k) + +- [2cnf] +- [3cnf] + +Up: [conjunctive_normal_form] + +See also: [clause_width] diff --git a/ltl b/ltl @@ -1,5 +1,7 @@ # LTL +[LTL_definition] + Has same expressive power as [FO] on [words] Up: [logic] diff --git a/memory_model_external b/memory_model_external @@ -0,0 +1,5 @@ +# External memory model + +https://en.wikipedia.org/wiki/External_memory_algorithm + +Up: [machine_model] diff --git a/monotone_cnf b/monotone_cnf @@ -0,0 +1,5 @@ +# Monotone cnf + +A [CNF] which is a [positive_Boolean_formula]: all [literals] are positive + +Up: [conjunctive_normal_form] diff --git a/nicomaques_theorem b/nicomaques_theorem @@ -0,0 +1,7 @@ +# Nicomaque's theorem + +https://fr.m.wikipedia.org/wiki/Somme_des_n_premiers_cubes + +The [sum] of the n first [cubes] is equal to the square of the [sum] of the n first [integers] + +Up: [theorem], [number] diff --git a/omega_automata b/omega_automata @@ -0,0 +1,9 @@ +# Omega automata + +- [muller_automaton] with [muller_acceptance] +- [buchi_automaton] with [buchi_acceptance] +- [parity_automaton] with [parity_acceptance] + +Up: [automata] + +See also: [word_infinite] diff --git a/pattern_with_variables_one_variable b/pattern_with_variables_one_variable @@ -0,0 +1,5 @@ +# Patterns with only one variable + +[kosolobov2017detecting] (also with reversal) + +Up: [pattern_with_variables] diff --git a/polynomial_multivariate b/polynomial_multivariate @@ -0,0 +1,5 @@ +# Polynomial multivariate + +A [polynomial] which involves multiple [variables] + +Up: [polynomial] diff --git a/s2p b/s2p @@ -0,0 +1,5 @@ +# S2p + +https://en.wikipedia.org/wiki/S2P_(complexity) + +Up: [complexity_class] diff --git a/sharp_satisfiability_fpras b/sharp_satisfiability_fpras @@ -0,0 +1,7 @@ +# Sharp-SAT FPRAS + +- [karp_luby] + +Up: [fpras] for [sharp_satisfiability_approximate] + +See also: [arenas2020fpras] diff --git a/squares_in_circles b/squares_in_circles @@ -0,0 +1,7 @@ +# Squares in circles + +https://en.m.wikipedia.org/wiki/Square_packing#In_a_circle + +See also: [squares_in_squares] + +Up: [packing_problem] diff --git a/squares_in_squares b/squares_in_squares @@ -0,0 +1,9 @@ +# Packing squares in squares + +https://en.wikipedia.org/wiki/Square_packing_in_a_square + +https://erich-friedman.github.io/packing/squinsqu/ + +Up: [packing_problem], [square] + +See also: [naturalness_research], [squares_in_circles] diff --git a/stack b/stack @@ -5,3 +5,5 @@ Up: [data_structure] See also: [stackexchange], [stack_overflow], [queue] + +Aliases: stacks diff --git a/tiling b/tiling @@ -0,0 +1,6 @@ +# Tiling + +https://en.wikipedia.org/wiki/Einstein_problem +- and without [reflection]: https://cs.uwaterloo.ca/~csk/spectre/ + +Up: [geometry] diff --git a/tree_binary b/tree_binary @@ -0,0 +1,7 @@ +# Tree binary + +A [tree] in which [internal_nodes] have at most two [children] + +- [tree_binary_full]: every [internal_node] has precisely two [children] + +Up: [tree] diff --git a/treelength b/treelength @@ -0,0 +1,10 @@ +# Treelength + +Minimal [diameter] of a [tree_decomposition] + +https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/tree_decomposition.html +- "While deciding whether a graph has [treelength] 1 can be done in linear time (equivalent to deciding if the graph is [chordal]), deciding if it has treelength at most k for any fixed constant k is [NP_complete] by [lokshtanov2010complexity]." + +Up: [width_measure] + +See also: [tree_depth], [treewidth], [pathwidth] diff --git a/tuple_generating_dependency_linear b/tuple_generating_dependency_linear @@ -0,0 +1,11 @@ +# Tuple generating dependency linear + +[tuple_generating_dependency] where [dependency_body] consists of a single fact + +It is in particular a [GTGD] + +- [inclusion_dependency] + +Up: [tuple_generating_dependency] + +Aliases: linear TGDs, linear TGD, linear tuple-generating dependency diff --git a/vector_addition_system b/vector_addition_system @@ -0,0 +1,21 @@ +# Vector addition system (VAS) + +- Like a [word_automaton] but with a configuration featuring a vector + - Transitions add a vector to the current vector + - They can only be taken if every coordinate remains positive + +[ginzburg1980vector]: determine when a VAS defines a [regular_language] + +Generalizations: +- [vector_addition_tree_automata] +- [vector_addition_system_pushdown] + +Complexity of the [reachability] problem: [ackermann_function] +- https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/ +- apparently still open when [dimension] is constant + +two-dimensional VAS with one test on counters, like [counter_automata]: [leroux2020reachability] + +Up: [automata] + +See also: [counter_automata] diff --git a/vector_addition_system_pushdown b/vector_addition_system_pushdown @@ -0,0 +1,9 @@ +# Vector addition system pushdown + +[vector_addition_system] with [pushdown_automaton] store + +Unclear if [reachability] is [decidable], cf [ganardi2022reachability] + +Also with counters and with resets [schmitz2019coverability] (but for [coverability]) + +Up: [vector_addition_system], [pushdown_automaton]