commit a84c99aad41f62ea80d1b8213ab3a1fbd84a9dc1 parent de1032058975fef2a96bcc692e2bf6b492655e6e Author: Antoine Amarilli <a3nm@a3nm.net> Date: Mon, 1 Jun 2026 22:41:27 +0200 Merge remote-tracking branch 'origin/master' Diffstat:
170 files changed, 603 insertions(+), 122 deletions(-)
diff --git a/1_planar_graph b/1_planar_graph @@ -0,0 +1,7 @@ +# 1 planar graph + +https://en.wikipedia.org/wiki/1-planar_graph + +Different from [crossing_number]: every [edge] has at most one crossing + +Up: [planar_graph] diff --git a/2cnf b/2cnf @@ -6,6 +6,6 @@ A [conjunctive_normal_form] [boolean_formula] where every [clause] contains two - generalization: [kcnf] - special case: [monotone2cnf] -Compilation to [OBDDs], cf [decolnet2026compilability] +Compilation to [OBDDs], cf [decolnet2026compilability] with [phase_transitions] Up: [conjunctive_normal_form] diff --git a/2sat b/2sat @@ -13,4 +13,4 @@ However: See also: [3sat], [Max_2sat] -Up: [sat_variants] +Up: [k_SAT] diff --git a/3sat b/3sat @@ -6,7 +6,7 @@ It is [np_complete] [3sat_variants] -Up: [sat_variants] +Up: [k_SAT] See also: [2sat], [schaefers_dichotomy_theorem] diff --git a/abokhamis2024fast b/abokhamis2024fast @@ -7,3 +7,5 @@ - connections with [information_theory] Up: [academic_paper] on [conjunctive_query_matrix_multiplication] + +Aliases: abokhamis2025fast diff --git a/ancestor b/ancestor @@ -6,4 +6,4 @@ Up: [tree] Aliases: ancestors -See also: [LCA] +See also: [LCA], [common_ancestor] diff --git a/antichain b/antichain @@ -2,6 +2,8 @@ In a [poset], an *antichain* is a subset of elements that are pairwise [incomparable] +- [smallest_antichain] + Up: [partial_order] See also: [antichain_coverage] diff --git a/automata_alternating b/automata_alternating @@ -6,8 +6,10 @@ Generalizes [NFAs] Can be seen as an [arena] in [game_theory] +- [automata_alternating_provenance] + Up: [automata_types] Aliases: alternating automaton, alternating automata -See also: [alternating_turing_machine] +See also: [alternating_turing_machine], [tree_automata_alternating] diff --git a/automata_nondeterministic b/automata_nondeterministic @@ -10,6 +10,8 @@ Special case: [automata_nondeterministic_dense] Generalization: [epsilonNFA] +Operations: [NFA_intersection] + Up: [one_way_automaton], [nondeterministic] See also: [epsilon_transition] diff --git a/automata_problems b/automata_problems @@ -8,6 +8,7 @@ On one [automaton]: - [automaton_cofiniteness] - [synchronizing_word_problem] - [counter_freeness_testing] +- [automaton_primality] On two [automata]: diff --git a/automata_reversible b/automata_reversible @@ -11,6 +11,6 @@ Class of [formal_language] accepted by a reversible automaton - membership given an [automata] can be tested in [ptime] - [pin1992reversible] -See also: [turing_machine_symmetric], [automata_symmetric], [transducer_reversible] +See also: [turing_machine_symmetric], [automata_symmetric], [transducer_reversible], [circuit_reversible] Up: [word_automaton] diff --git a/automatic_relation b/automatic_relation @@ -20,6 +20,6 @@ It is an [open_problem] whether the [computational_problem] of deciding [formal_ Up: [automata], [relation] -See also: [automatic_structure], [automatic_graph], [sequence_automatic], [post_correspondence_problem] +See also: [automatic_structure], [automatic_graph], [sequence_automatic], [post_correspondence_problem], [perfect_shuffle] Aliases: automatic relations diff --git a/automaton_emptiness b/automaton_emptiness @@ -4,4 +4,4 @@ It is [nl_complete] to check [automaton] emptiness Up: [automata_problems], [language_emptiness] -See also: [automaton_finiteness], [universality_automata], [intersection_nonemptiness] +See also: [automaton_finiteness], [universality_automata], [intersection_nonemptiness], [automaton_nonemptiness] diff --git a/automaton_intersection b/automaton_intersection @@ -2,9 +2,8 @@ can be done with [product_construction] -[computational_complexity] bounds on [automaton_emptiness] of intersection of constant number of [DFAs] (especially on [intersection_nonemptiness]): [oliveira2018intersection] and [oliveira2020fine] -- connections to [3SUM] and [triangle_detection] -- also [ascone2025are] on [regular_expressions] (for [intersection_nonemptiness]) +- [DFA_intersection] +- [NFA_intersection] Up: [automaton_constructions], [intersection] diff --git a/automaton_primality b/automaton_primality @@ -0,0 +1,7 @@ +# Automaton primality + +decide if an input DFA can be written as the [automaton_intersection] of input DFAs that all have strictly less states + +it in [NP_hard] to decide, see [spenner2026deciding] + +Up: [automata_problems] diff --git a/bayes_network b/bayes_network @@ -7,3 +7,5 @@ Can be "tree-structured Bayes network", or have bounded [treewidth] Up: [probabilistic_graphical_model] See also: [message_passing], [treewidth] + +Aliases: bayesian network, bayesian networks, bayes networks diff --git a/bdd b/bdd @@ -10,3 +10,5 @@ Up: [diagram] See also: [branching_program], [read_once_branching_program], [decision_tree], [read_twice_branching_program] + +Aliases: binary decision diagram, binary decision diagrams, BDDs diff --git a/bodirsky2024symmetric b/bodirsky2024symmetric @@ -5,5 +5,8 @@ - [datalog_monadic] - [datalog_arc_monadic] - [datalog_symmetric_linear_arc_monadic] +- [linear_datalog_conjecture] Up: [academic_paper] on [constraint_satisfaction_problem_datalog] + +See also: [kazda2019npermutability] diff --git a/boolean_function_classes b/boolean_function_classes @@ -4,6 +4,7 @@ - [positive_threshold_function] - [boolean_function_regular] - [boolean_function_evasive] +- [boolean_function_unate] Up: [boolean_function] diff --git a/boolean_valuation b/boolean_valuation @@ -8,6 +8,6 @@ A [function] mapping a set X to [Boolean] values Up: [function], [valuation], [boolean] -See also: [boolean_function] +See also: [boolean_function], [partial_boolean_valuation] -Aliases: assignment, Boolean assignment, assignments, Boolean assignments +Aliases: assignment, Boolean assignment, assignments, Boolean assignments, Boolean valuations diff --git a/boundary_operation b/boundary_operation @@ -0,0 +1,9 @@ +# Boundary operation + +the *boundary* of a [language] L is L^* cap (L^c)^* + +studied, e.g., in [jirasek2026boundary] + +Up: [formal_language_operator] + +See also: [kleene_star], [language_complement], [language_intersection] diff --git a/burrows_wheeler_transform b/burrows_wheeler_transform @@ -2,6 +2,8 @@ [gagie2017wheeler] -Up: [stringology], [compression_string] +Up: [text_algorithm], [compression_string] See also: [wheeler_nfa] + +Aliases: BWT diff --git a/chase_termination b/chase_termination @@ -8,7 +8,9 @@ depends on whether you want all instances or an input instance [academic_papers]: - [gogacz2014all] -- recent work: [hanisch2024chase] - - idea: beyond [ptime] [data_complexity] +- recent work: + - [hanisch2024chase] + - idea: beyond [ptime] [data_complexity] + - [larroque2026when] Up: [chase], [termination] diff --git a/chebyshevs_inequality b/chebyshevs_inequality @@ -7,3 +7,5 @@ Pr[|X - EX| \geq epsilon EX] \leq (Var X) epsilon^2 (EX)^2 Up: [concentration_inequality] See also: [expectation], [variance] + +Aliases: Chebyshev inequality, Chebyshef inequality, Chebyshef's inequality diff --git a/circuit_algebraic b/circuit_algebraic @@ -5,3 +5,5 @@ Up: [probabilistic_circuit], [algebra] Aliases: algebraic circuit, algebraic circuits + +See also: [algebraic_decision_diagram] diff --git a/circuit_classes b/circuit_classes @@ -8,6 +8,8 @@ In [circuit_complexity]: - [acc] ACC, [acc0], etc. - liens avec [solvable_group] -Up: [circuit] +In [knowledge_compilation]: see [knowledge_compilation_classes] + +- [reversible_circuits] -See also: [knowledge_compilation_classes] +Up: [circuit] diff --git a/circuit_equivalence_ddnnfs b/circuit_equivalence_ddnnfs @@ -1,5 +1,9 @@ # Circuit equivalence d-DNNFs -It is in [coRP]: [darwiche2002testing] +The [circuit_equivalence_problem] on [d-DNNFs] is in [coRP]: [darwiche2002testing] -Up: [circuit_equivalence], [d-DNNF] +Up: [circuit_equivalence_problem], [d-DNNF] + +Aliases: dDNNF_equivalence + +See also: [polynomial_identity_testing] diff --git a/circuit_multivalued b/circuit_multivalued @@ -12,6 +12,6 @@ Enforcing [circuit_structuredness], or enforcing [circuit_determinism], results Up: [circuit] -See also: [Factorized_database], [multivalued_formula] +See also: [Factorized_database], [multivalued_formula], [multivalued_decision_diagram] Aliases: multivalued circuit, multivalued circuits diff --git a/circuit_negation b/circuit_negation @@ -0,0 +1,11 @@ +# Circuit negation + +The [negation] operator applied to a [circuit] + +[computational_problem]: [negation_problem] + +Up: [negation] of [circuit] + +See also: [de_morgan's_law] + +Aliases: circuit negated, circuit complement, circuit complementation, circuit negations diff --git a/circuit_trace b/circuit_trace @@ -8,4 +8,4 @@ Up: [circuit] See also: [parse_tree], [proof_tree] -Aliases: certificate +Aliases: certificate, trace, traces diff --git a/complementation b/complementation @@ -8,3 +8,5 @@ Up: [logic], [boolean_operator] Aliases: complement, complements + +See also: [negation] diff --git a/complexity_class b/complexity_class @@ -7,6 +7,7 @@ - [logspace] - [complexity_time]: [complexity_time_classes] - [spanl] +- [PPA] ## [complexity_hierarchy] diff --git a/complexity_space b/complexity_space @@ -9,4 +9,4 @@ Up: [complexity_measure] See also: [complexity_time] -Aliases: space complexity +Aliases: space complexity, computational space diff --git a/complexity_time b/complexity_time @@ -8,4 +8,4 @@ Up: [complexity_measure] See also: [complexity_space] -Aliases: time complexity +Aliases: time complexity, computational time diff --git a/concentration_inequality b/concentration_inequality @@ -6,3 +6,5 @@ - [hoeffdings_inequality] Up: [inequality_mathematics], [probabilities] + +Aliases: concentration bound diff --git a/conjunctive_query b/conjunctive_query @@ -18,4 +18,4 @@ Up: [query_language] See also: [conjunction] -Aliases: CQ, CQs +Aliases: CQ, CQs, conjunctive queries diff --git a/constant_delay b/constant_delay @@ -5,3 +5,5 @@ An [enumeration_algorithm] is *constant delay* if its [enumeration_delay] is bou Up: [enumeration_delay] See also: [linear_preprocessing_constant_delay] + +Aliases: enumeration constant delay, constant delay enumeration diff --git a/counting_problem b/counting_problem @@ -7,10 +7,10 @@ - [triangle_counting] - [maximal_independent_set_counting] - [subgraph_counting] + - [counting_simple_paths] - [counting_query_answers] - [counting_cqs] - For [satisfiability_boolean]: [sharp_satisfiability] -- [counting_simple_paths] - [sharp_automaton]: - [sharp_nfa], cf [arenas2020efficient] - [sharp_ufa] diff --git a/counting_query_answers b/counting_query_answers @@ -7,3 +7,5 @@ The [counting_problem] of [counting] the answers to a [query] - [rpq_counting_answers] Up: [counting_problem] + +Aliases: query answer counting, answer counting diff --git a/counting_simple_path_approximate b/counting_simple_path_approximate @@ -0,0 +1,11 @@ +# Approximate counting of simple paths + +Given a [graph], can we do [approximate_counting] for the [counting_problem] of [counting_simple_paths]? + +No: there is no [FPRAS] unless [RP] = [NP], cf [yamamoto2017approximately] + +This applies for [undirected_graphs] and for [directed_graphs], and with fixed endpoints or without fixed endpoints + +Up: [counting_simple_path] + +Aliases: approximate counting simple paths, approximate counting of simple paths diff --git a/courcelle_theorem b/courcelle_theorem @@ -8,6 +8,8 @@ Also: bounded [cliquewidth] if we are given a witness of cliquewidth time f(|phi|, width) times linear in the graph +[courcelle_logspace] + Up: [theorem] on [monadic_second_order_logic_model_checking], [algorithmic_metatheorem] Aliases: Courcelle's theorem diff --git a/crossing_number b/crossing_number @@ -14,4 +14,4 @@ The crossing number of [complete_bipartite_graphs] is an [open_problem], cf http Up: [planar_graph] -See also: [single_crossing_graph] +See also: [single_crossing_graph], [1_planar_graph] diff --git a/cycle_circuit b/cycle_circuit @@ -0,0 +1,5 @@ +# Circuit + +A [cycle] where the same [vertices] (but not [edges]) can be visited multiple times + +Up: [cycle] diff --git a/data_complexity b/data_complexity @@ -6,4 +6,4 @@ introduced in [vardi1982complexity] Up: [database_theory_complexity] -See also: [combined_complexity], [query_complexity] +See also: [combined_complexity], [query_complexity], [data_complexity_classifications] diff --git a/data_word b/data_word @@ -1,10 +1,12 @@ # Data word -like [word] but on an infinite or very large alphabet +Like [words] 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) +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] + +Aliases: data words diff --git a/datalog b/datalog @@ -48,6 +48,7 @@ - [datalog_grounding] - [datalog_rewriting] - [datalog_course] +- [datalog_conference] Up: [query_language] diff --git a/datalog_linear b/datalog_linear @@ -9,3 +9,5 @@ occurs in [bodirsky2024symmetric] Up: [datalog] Aliases: linear Datalog + +See also: [linear_datalog_conjecture] diff --git a/datalog_negation_provenance b/datalog_negation_provenance @@ -1,6 +1,6 @@ # Datalog negation provenance -[bogaerts2025why] +[bogaerts2025why] [bogaerts2026why] Up: [datalog_negation], [datalog_provenance] diff --git a/datalog_query_evaluation b/datalog_query_evaluation @@ -19,6 +19,8 @@ An important idea is to run the [CQs] of the [rule_bodies] efficiently: [conjunc [zhang2023enhancing]: [query_evaluation] of [datalog] via [hypertreewidth] +- [datalog_fine_grained] + Up: [datalog], [query_evaluation] See also: [query_optimization] diff --git a/ddnnf b/ddnnf @@ -10,4 +10,4 @@ Up: [knowledge_compilation_classes], [dd] See also: [dnnf], [decision_dnnf], [uobdd], [times_uplus_circuit] -Aliases: d-DNNFs +Aliases: d-DNNFs, d DNNF, d DNNFs diff --git a/de_bruijn_sequence b/de_bruijn_sequence @@ -1,5 +1,7 @@ # De bruijn sequence +https://en.wikipedia.org/wiki/De_Bruijn_sequence + like [universal_word] but for [cyclic_word] See also: [universal_word] diff --git a/decdnnf_negation b/decdnnf_negation @@ -0,0 +1,6 @@ +# DecDNNF negation + +open whether [decDNNFs] can be negated to a [decDNNF] +- cf [decolnet2022hard] p124 + +Up: [negation_problem] of [dec_DNNF] diff --git a/decision b/decision @@ -9,3 +9,5 @@ other name: "syntactic unambiguity" Up: [circuit_condition] See also: [decision_problem] + +Aliases: decision determinism diff --git a/decision_dnnf b/decision_dnnf @@ -7,6 +7,8 @@ A *decision-DNNF* is a [DNNF] but only with [decision_gates] See [cali2026complexity] -Up: [dnnf] +[circuit_negation]: see [decDNNF_negation] -Aliases: decision_DNNFs, decision-DNNF, decision-DNNFs, decDNNF, decDNNFs +Up: [dnnf], [decision_determinism] + +Aliases: decision_DNNFs, decision-DNNF, decision-DNNFs, decDNNF, decDNNFs, dec DNNF, dec DNNFs diff --git a/decision_sdnnf b/decision_sdnnf @@ -3,3 +3,5 @@ A [decision_dnnf] which is a [structured_circuit] Up: [decision_dnnf], [sdnnf] + +Aliases: structured decision DNNF, structured dec DNNF, structured decDNNF,structured decision DNNFs, structured dec DNNFs, structured decDNNFs diff --git a/density_function b/density_function @@ -16,6 +16,6 @@ computing its regime on [context_free_languages]: [gawrychowski2010finding] Up: [automata] -See also: [universality_automata], [sharp_automaton], [slice], [degree_of_ambiguity], [growth_rate_analysis] +See also: [universality_automata], [sharp_automaton], [slice], [degree_of_ambiguity], [growth_rate_analysis], [density] Aliases: density functions diff --git a/dfa_intersection b/dfa_intersection @@ -0,0 +1,7 @@ +# DFA intersection + +[computational_complexity] bounds on [automaton_emptiness] of intersection of constant number of [DFAs] (especially on [intersection_nonemptiness]): [oliveira2018intersection] and [oliveira2020fine] +- connections to [3SUM] and [triangle_detection] +- also [ascone2025are] on [regular_expressions] (for [intersection_nonemptiness]) + +Up: [automaton_intersection], [DFA] diff --git a/diagram b/diagram @@ -13,6 +13,6 @@ Up: [knowledge_compilation_classes] -See also: [read_once], [decision_tree] +See also: [read_once], [decision_tree], [zero_suppressed_semantics] Aliases: decision diagram, decision diagrams, diagrams diff --git a/disjunctive_normal_form_orthogonal b/disjunctive_normal_form_orthogonal @@ -3,14 +3,14 @@ [disjunctive_normal_form] where for any two [terms] they are not mutually satisfiable - so it is an [unambiguous] [disjunctive_normal_form] -[complement]: [hitting_cnf] +Their [circuit_negations] are [hitting_cnfs] 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] +The [negation_problem] on them: [disjunctive_normal_form_orthogonal_negation] Generalization: [k_unambiguous_DNF] Up: [disjunctive_normal_form] -Aliases: unambiguous DNF, unambiguous DNFs, orthogonal DNF, orthogonal DNFs +Aliases: unambiguous DNF, unambiguous DNFs, orthogonal DNF, orthogonal DNFs, uDNF, uDNFs diff --git a/dsdnnf b/dsdnnf @@ -10,4 +10,4 @@ Restriction: [TDDs], cf [capelli2026canonical] Up: [knowledge_compilation_classes], [ddnnf], [sdnnf] -Aliases: dSDNNFs, d_SDNNFs, d_SDNNF +Aliases: dSDNNFs, d_SDNNFs, d_SDNNF, structured dDNNF, structured d_DNNF, structured dDNNFs, structured d_DNNFs diff --git a/dynamic_membership_word b/dynamic_membership_word @@ -12,6 +12,7 @@ Depends on which [updates_word] are allowed: - [dynamic_membership_conditional] - [dynamic_membership_append_only] - for [regular_expressions_counting]: [bjorklund2015succinct] +- for [data_words]: [alpay2026support] Up: [dynamic_membership], [dynamic_word] diff --git a/edge_coloring b/edge_coloring @@ -1,8 +1,18 @@ # Edge coloring +A function mapping the [edges] of an [undirected_graph] to colors such that no two incident edges get the same color + +An easy lower bound on the number of colors required is the [maximum_degree] + +[Vizings_theorem]: the number of colors needed is always at most the [maximum_degree] plus one + +It is [NP_hard] to determine which of the two applies + +Computing edge colorings whose number of colors is the [maximum_degree] plus one can now be done in [near_linear_time] + - [incremental_maintenance_edge_coloring] -- [vizings_theorem] - [2_edge_coloring] +- [online_edge_coloring] Up: [graph_coloring] diff --git a/enumeration_cqs b/enumeration_cqs @@ -13,3 +13,5 @@ With [self_joins]: [enumeration_self_joins] Up: [enumeration_query_answers] for [conjunctive_query] See also: [direct_access] + +Aliases: CQ enumeration diff --git a/enumeration_query_answers b/enumeration_query_answers @@ -7,3 +7,5 @@ tool: [query_cover] Up: [enumeration] + +Aliases: query enumeration diff --git a/enumeration_spanner b/enumeration_spanner @@ -2,6 +2,7 @@ - [amarilli2019constant] - [enumeration] by [cristian] et al.: [rematch] +- [gawrychowsi2026optimal] Up: [enumeration] for [spanner] diff --git a/enumeration_tasks b/enumeration_tasks @@ -24,5 +24,6 @@ - https://cstheory.stackexchange.com/questions/36334/enumerating-topological-sorts-of-a-vertex-labeled-dag - [enumeration_valuations] - [enumeration_posets] +- [enumeration_regular_languages] Up: [enumeration] diff --git a/enumeration_techniques b/enumeration_techniques @@ -1,5 +1,7 @@ # Enumeration techniques +for a [survey], cf [capelli2026enumeration] + - [union_trick] by [arnaud_durand] and [yann_strozecki] - cf [berkholz2020constantb] Theorem 2.1 - [proximity_search], enumeration framework (cf [wepa_2022]) diff --git a/enumeration_ucqs b/enumeration_ucqs @@ -19,3 +19,5 @@ open question: [enumeration_ucqs_classifying] Up: [enumeration] for [union_of_conjunctive_query] See also: [enumeration_cqs] + +Aliases: UCQ enumeration diff --git a/erdos_distinct_distances_problem b/erdos_distinct_distances_problem @@ -0,0 +1,11 @@ +# Erdos distinct distances problem + +https://en.wikipedia.org/wiki/Erd%C5%91s_distinct_distances_problem + +A question about the minimal number of distinct edge distances can be achieved by a planar embedding of a graph (the maximal number is easy to achieve) + +Known to be Omega(n / log n) and O(n / sqrt(log n)) + +See also: [unit_distance_conjecture] + +Up: [extremal_combinatorics] diff --git a/eulerian_circuit b/eulerian_circuit @@ -1,9 +1,11 @@ # Eulerian circuit -An [Eulerian_path] which is a [cycle_circuit], i.e., starts and ends at the same [vertex] +A [Eulerian_trail] which is a [cycle_circuit], i.e., starts and ends at the same [vertex] The number of Eulerian circuits in [directed_graphs] can be computed in [PTIME] by the [BEST_theorem] +- [Eulerian_circuit_counting] + Up: [eulerian_path] -Aliases: Eulerian cycle +Aliases: Eulerian cycle, Eulerian circuits diff --git a/eulerian_path b/eulerian_path @@ -1,11 +1,16 @@ # Eulerian path -A [path] that visits every [edge] of a [graph] exactly once +A [trail] that visits every [edge] of a [graph] exactly once Can be defined for [graph_directed] or [graph_undirected] [Decision_problem]: [Eulerian_path_decision] +Also: + +- [Eulerian_trail_counting] +- [Eulerian_trail_enumeration] + Variants: - [eulerian_cycle] - [chinese_postman_problem] @@ -13,3 +18,5 @@ Variants: Up: [path] See also: [Eulerian_partitioning] + +Aliases: Eulerian trail diff --git a/eulerian_trail_enumeration b/eulerian_trail_enumeration @@ -0,0 +1,5 @@ +# Eulerian trail enumeration + +see [bals2026optimal] + +Up: [enumeration], [eulerian_path] diff --git a/exponentiation b/exponentiation @@ -9,4 +9,4 @@ Up: [mathematics_operation] See also: [exptime], [semigroup], [multiplication], [power_mathematics], [square_root] -Aliases: exponent, exponents +Aliases: exponent, exponents, exponential, exponentials diff --git a/fbdd b/fbdd @@ -4,6 +4,8 @@ Free [BDD], i.e., the [variables] are not [ordered] but every [path] in the [BDD Is a subclass of [DNNF] +Can be [circuit_negated] in [PTIME] by swapping the [sinks] + Up: [bdd] Aliases: FBDDs diff --git a/finite_model_theory b/finite_model_theory @@ -4,4 +4,4 @@ Up: [model_theory], [finite] -See also: [Open_world_query_answering] +See also: [Open_world_query_answering], [finite_model] diff --git a/fo2 b/fo2 @@ -5,6 +5,7 @@ extensions: - [c2] with [counting_quantifier] - [gc2] with [guarded_fragment] quantification +- with [nested_equivalence_relations], cf [fiuk2025two] FO2 on [words] with order cannot define [successor]: you need [FO3] - with [successor], it defines a variety of [semigroups] diff --git a/formal_language_operator b/formal_language_operator @@ -18,6 +18,8 @@ An [operator] that takes one or two [formal_languages] and creates a new [formal - [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] +- [boundary_operation] +- [formal_language_square_root] Up: [formal_language], [operator] diff --git a/formal_language_square b/formal_language_square @@ -0,0 +1,7 @@ +# Formal language square + +The *square* of a [formal_language] L is the language of the words uu such that u in L + +See also: [formal_language_square_root], [square_language] + +Up: [formal_language_operator], [square] diff --git a/formal_language_square_root b/formal_language_square_root @@ -0,0 +1,11 @@ +# Formal language square root + +The *square root* of a [formal_language] L is the language of the words u such that uu in L + +The square root of a [regular_language] is a [regular_language] + +[state_complexity] studied in [onishchenko2026nondeterministic] + +Up: [formal_language_operator], [square_root] + +See also: [formal_language_square] diff --git a/formal_language_theory b/formal_language_theory @@ -55,6 +55,7 @@ Studies [formal_languages] - [interchange_lemma] https://en.wikipedia.org/wiki/Interchange_lemma - other such results: https://cstheory.stackexchange.com/a/54032 - [myhill_nerode_theorem] +- [factorization_forest] Up: [theoretical_computer_science] diff --git a/gql b/gql @@ -4,4 +4,8 @@ - [francis2023gpc] introduces [gpc] which is equivalent to GQL but easier to understand - [figueira2025complexity] studies the [computational_complexity] of [query_evaluation] +is about [property_graph] databases + Up: [graph_query_languages_standards] + +See also: [sparql], [GraphQL] diff --git a/graph_database_practical b/graph_database_practical @@ -4,6 +4,7 @@ Implementations: - [Neo4j] - for [RPQs]: [garcia2025pathdb] +- [apache_jena] Query languages: diff --git a/graph_family b/graph_family @@ -45,6 +45,10 @@ A (generally [infinite]) set of [graphs] - [leaf_power] +- [unit_distance_graph] + +- [graph_word_representable] + May have the property of being [graph_class_hereditary] Up: [graph] diff --git a/graph_labeling b/graph_labeling @@ -4,6 +4,7 @@ - [distance_labeling]: cf [gawrychowski2023better] - [graceful_labeling] - [canonical_labeling] +- [adjacency_labeling] Up: [graph] diff --git a/graph_modification_problem b/graph_modification_problem @@ -5,6 +5,8 @@ - for [treewidth]: [graph_modification_treewidth] +- [graph_deletion_problem] + Up: [graph_modification] Aliases: graph modification problems diff --git a/graph_modification_treewidth b/graph_modification_treewidth @@ -2,4 +2,4 @@ - reducing [treewidth] by removing [graph] [edges]: [marchand2022tree] -Up: [treewidth], [graph_modification] +Up: [treewidth], [graph_deletion] diff --git a/graph_packing b/graph_packing @@ -12,6 +12,8 @@ Can be with [induced_subgraphs] (a "strict factor") [kirkpatrick1983complexity]: the packing problem with [induced_subgraphs] when the [graph] to pack has at least 3 vertices is [NP_complete] +[hell1986packings], includes packings by [stars] + Up: [computational_problem] on [graph] See also: [packing_problem], [graph_partition], [path_cover], [path_partition] diff --git a/graph_query_languages b/graph_query_languages @@ -28,9 +28,12 @@ Also: - [graph_query_languages_practical] - [graph_query_languages_standards] +- [graph_query_languages_features] Historically: [cruz1987graphical] Up: [graph_database] See also: [fixpoint], [self_join] + +Aliases: graph query language diff --git a/graph_theorem b/graph_theorem @@ -4,7 +4,11 @@ - [four_color_theorem] - [strong_perfect_graph_theorem] - [123_conjecture] +- [friendship_theorem] +- [handshaking_lemma] -Up: [graph] +Up: [graph], [theorems] Aliases: graph theorems + +See also: [graph_theory] diff --git a/graph_theory b/graph_theory @@ -1,9 +1,15 @@ # Graph theory -- [friendship_theorem] -- [handshaking_lemma] -- [extremal_graph_theory] +## Subfields + - [games_on_graphs] - [pursuit_evasion] +- [extremal_graph_theory] +- [structural_graph_theory] +- [graph_algorithms] + +## Graph theorems + +[graph_theorems] Up: [theoretical_computer_science] on [graph] diff --git a/graph_weighted b/graph_weighted @@ -1,6 +1,6 @@ # Graph weighted -A [graph] where [edges] carry [weight] +A [graph] where [edges] carry [edge_weights] [Graph_algorithms] to typically run on such graphs: - [shortest_path] diff --git a/grid_graph b/grid_graph @@ -6,6 +6,6 @@ Up: [graph_family] -See also: [wall_graph] +See also: [wall_graph], [grid_embedding] Aliases: grid graphs, grid diff --git a/guarded_fixpoint_logic b/guarded_fixpoint_logic @@ -2,6 +2,8 @@ Does not have the [finite_model_property], see [barany2012finite] +Generalizations: [GNFP] + Up: [guarded_fragment], [fixpoint] Aliases: muGF diff --git a/hadwiger_conjecture b/hadwiger_conjecture @@ -0,0 +1,9 @@ +# Hadwiger conjecture + +https://en.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory) + +Asks whether every [graph] with [chromatic_number] k have a k-[clique] as a [graph_minor] + +Up: [graph_coloring] + +See also: [Hadwiger_nelson_problem] diff --git a/hitting_cnf b/hitting_cnf @@ -7,3 +7,5 @@ A [conjunctive_normal_form] where the [disjunction] of any two [clauses] is [tau Up: [conjunctive_normal_form] See also: [hitting_set] + +Aliases: hitting CNFs diff --git a/induced_subgraph b/induced_subgraph @@ -8,4 +8,4 @@ See also: [subgraph], [graph_minor], [induced_subhypergraph], [induced_cycle], [ Up: [graph] -Aliases: induced subgraphs +Aliases: induced subgraphs, vertex induced subgraph, vertex induced subgraphs diff --git a/induced_subinstance b/induced_subinstance @@ -0,0 +1,9 @@ +# Induced subinstance + +A [subinstance] defined by a subset of the [active_domain] + +See also: [induced_subgraph], [induced_subhypergraph] + +Up: [subinstance] + +Aliases: vertex induced subinstance diff --git a/jumping_automata_on_graphs b/jumping_automata_on_graphs @@ -0,0 +1,8 @@ +# Jumping automata on graphs + +- [lower_bounds] on [directed_st_connectivity], [barnes1998time] +- [lower_bounds] on [undirected_st_connectivity], [edmonds1993time] + +Up: [machine_model] + +Aliases: JAG diff --git a/k_sat b/k_sat @@ -0,0 +1,8 @@ +# K SAT + +[SAT] but with [CNFs] of [clause_width] at most k + +- [2SAT] +- [3SAT] + +Up: [sat_variants] diff --git a/knowledge_compilation b/knowledge_compilation @@ -16,3 +16,5 @@ Classes of [circuits] for which some tasks are tractable Up: [theoretical_computer_science] Aliases: KC + +See also: [provenance_circuit] diff --git a/knowledge_compilation_classes b/knowledge_compilation_classes @@ -1,15 +1,20 @@ # Knowledge compilation classes -- [decomposable] [dnnf] -- [sdnnf], with [structuredness] -- [ddnnf], with [deterministic] +- [negation_normal_form] +- [decomposability] + - [DNNF] + - [wDNNF] +- [structuredness] + - [SDNNF] +- [circuit_determinism]: [d-DNNF] - exponentially separated from [dnnf] - [sauerhoff_function] - [ordered_dnnf], in [amarilli2017circuit] -- [smoothing] -- [sdd] +- [smoothness] +- [SDD] - exponentially separated from [obdd] - [hidden_weighted_bit_function] +- [TDD] - [decision_dnnf] - [decision_sdnnf] - [ordered_decision_circuit] @@ -18,10 +23,10 @@ - [nobdd] - [uobdd] - [fbdd] - - [zero_suppressed_semantics] + - see also: [zero_suppressed_semantics] Up: [knowledge_compilation], [circuit], [Boolean_function_representation] See also: [circuit_classes], [circuit_condition] -Aliases: knowledge compilation circuit classes, knowledge compilation circuits +Aliases: knowledge compilation circuit classes, knowledge compilation circuits, knowledge compilation class, kc circuit class, kc circuit classes, knowledge compilation circuit class diff --git a/l_poly b/l_poly @@ -5,3 +5,5 @@ https://en.wikipedia.org/wiki/L/poly Up: [complexity_class], [logspace], [advice] See also: [p_poly] + +Aliases: L slash poly diff --git a/laminar_set_family b/laminar_set_family @@ -5,3 +5,5 @@ From a set, partition it into disjoint subsets, and then recursively decompose t See also: [conjunctive_query_hierarchical] Up: [mathematics] + +Aliases: laminar set families diff --git a/lawler_murty b/lawler_murty @@ -0,0 +1,11 @@ +# Lawler-Murty procedure + +An [enumeration_technique], described in [lawler1972procedure] + +cf slide 30 of <https://northeastern-datalab.github.io/topk-join-tutorial/slides/Anyk-Tutorial-Part3-RankedEnumeration.pdf> + +See also: [flashlight_search] + +Up: [enumeration_technique] + +Aliases: Lawler Murty procedure, Lawler-Murty procedure, Lawler-Murty diff --git a/linear_datalog_conjecture b/linear_datalog_conjecture @@ -0,0 +1,6 @@ +# Linear datalog conjecture + +mentionde in [bodirsky2024symmetric]: is it true that every +[finite_domain_CSP] which is in [NL] can be solved by a [linear_Datalog] program + +Up: [conjecture], [datalog_linear] diff --git a/lower_bounds b/lower_bounds @@ -5,6 +5,6 @@ Up: [computational_complexity] -See also: [theorem], [upper_bound] +See also: [theorem], [upper_bound], [lower_bound_techniques] Aliases: lower bound diff --git a/lowest_common_ancestor b/lowest_common_ancestor @@ -6,4 +6,4 @@ Up: [tree] Aliases: LCA -See also: [Lowest_common_ancestor_problem] +See also: [Lowest_common_ancestor_problem], [common_ancestor] diff --git a/machine_model b/machine_model @@ -5,6 +5,7 @@ - [cell_probe_model] - [automata] - [transducers] +- [jumping_automata_on_graphs] Up: [theoretical_computer_science] diff --git a/maximal_degree b/maximal_degree @@ -10,3 +10,5 @@ Special cases: - see also [cubic_graph], where the degree of each vertex is 3 Up: [degree], [maximum] + +Aliases: maximum degree diff --git a/multiple_context_free_grammar b/multiple_context_free_grammar @@ -5,3 +5,5 @@ Up: [context_free_grammar] Aliases: MCFG, MCFGs + +See also: [multiple_context_free_language] diff --git a/negation b/negation @@ -6,6 +6,7 @@ - [datalog_negation] - [negation_as_failure] - [first_order_logic_existential_positive] +- [circuit_negation] Up: [logic] diff --git a/negation_normal_form b/negation_normal_form @@ -0,0 +1,15 @@ +# Negation normal form + +[Boolean_circuits] using [OR], [AND], [literal_gates], and [cosntant_gates] + +Hence, [negation] is only at the leaves + +Subclasses: + +- [DNNF] + +All [knowledge_compilation_queries] are (conditionally) intractable on the class ; some [knowledge_compilation_transformations] are tractable and others not + +Up: [knowledge_compilation_classes] + +Aliases: NNF diff --git a/nfa_acceptance b/nfa_acceptance @@ -1,10 +1,12 @@ # NFA acceptance -The [automaton_acceptance] problem for an [NFA] +The [automaton_acceptance] problem for an [NFA], of course in [combined_complexity] Can be solved by [state_set_simulation] -[Hardness_hypothesis] that this is optimal in [backurs2016which], see also [bringmann2024nfa] +[Hardness_hypothesis] that this is optimal in [backurs2016which] + +[NFA_acceptance_classification] Up: [automaton_acceptance], [NFA] diff --git a/nfa_acceptance_hypothesis b/nfa_acceptance_hypothesis @@ -4,4 +4,10 @@ Hypothesis 2 in [bringmann2024nfa] Implies [OMV_hypothesis] +It is the hypothesis that you cannot test acceptance of a word of length n by an [NFA] of size m in O((mn)^{1-ε}) for any ε *even for dense NFAs* + +The standard [Backurs_Indyk] result says you cannot test acceptance of a word of length n by an [NFA] with m states in O((mn)^{1-ε}) for any ε + +Note that for a [regular_expression] this makes no difference because a regular expression of size m can be converted to an [NFA] with O(m) states + Up: [bringmann2024nfa], [computational_hypothesis] diff --git a/nfa_intersection b/nfa_intersection @@ -0,0 +1,8 @@ +# NFA intersection + +Can be done with the [product_construction] + +See [chistikov2026intersecting] for a more efficient algorithm in terms of the number of [transitions] +- works via [perfect_shuffle] + +Up: [automaton_intersection], [NFA] diff --git a/nobdd b/nobdd @@ -9,3 +9,5 @@ See also: [nrobp] Up: [nfbdd] + +Aliases: nOBDDs diff --git a/obdd b/obdd @@ -8,7 +8,11 @@ A [deterministic] [bdd] with a [variable_order] We can tractably take the [conjunction] and [disjunction] of two OBDDs where the [variable_order] is the same - [OBDD_conjunction] -Generalization: [CFLOBDDs] +Generalizations: +- [CFLOBDDs] +- [FBDDs] + +Notion: [bdd_width] Up: [bdd] diff --git a/p_poly b/p_poly @@ -5,3 +5,5 @@ Up: [complexity_class], [ptime], [advice] See also: [l_poly] + +Aliases: P slash poly diff --git a/palindrome_language b/palindrome_language @@ -4,4 +4,4 @@ The [formal_language] of the [words] that are [palindromes] Up: [formal_language], [palindrome] -See also: [square_language] +See also: [square_language], [anderson2009detecting] diff --git a/pattern_matching_algorithm b/pattern_matching_algorithm @@ -5,4 +5,4 @@ - [knuth_morris_pratt] - [rabin_karp] with [rolling_hash] -Up: [algorithm] for [pattern_matching] +Up: [text_algorithm] for [pattern_matching] diff --git a/planar_graph b/planar_graph @@ -32,10 +32,12 @@ Generalizations: - to [hypergraphs]: [planar_hypergraph] - to [directed_graphs]: [directed_planar_graph] -- to quantify the "degree of non-planarity": [crossing_number] -- [single_crossing_graph] +- to quantify the "degree of non-planarity": + - [crossing_number] + - [single_crossing_graph] + - [1_planar_graph] -See also: [graph_drawing], [planar_separator_theorem] +See also: [graph_drawing], [planar_separator_theorem], [grid_embedding] Up: [graph] diff --git a/probabilistic_graphical_model b/probabilistic_graphical_model @@ -1,6 +1,7 @@ # Probabilistic graphical model - [bayes_network] +- [markov_network] - [markov_logic_network] - [sum_product_network] diff --git a/provenance b/provenance @@ -42,3 +42,5 @@ Kinds of provenance: See also: [explainability], [artificial_intelligence_explainable], [pqe] Up: [research] + +Aliases: data provenance diff --git a/provenance_circuit b/provenance_circuit @@ -4,6 +4,10 @@ Can use [circuit] for [provenance], e.g., - [datalog] provenance: [provenance_circuit_datalog] - [provenance_mso]: [monadic_second_order_logic] provenance [amarilli2015provenance] +- [provenance_fo] +- [provenance_cq] + - [provenance_ucq] +- [provenance_rpq] Up: [provenance], [circuit] diff --git a/provenance_datalog b/provenance_datalog @@ -16,6 +16,6 @@ Subcases: For [datalog_extensions]: - [datalog_negation_provenance] -- [bogaerts2025why] pour [datalog_with_negation] +- [bogaerts2025why] [bogaerts2026why] pour [datalog_with_negation] Up: [provenance], [datalog] diff --git a/query_answer b/query_answer @@ -2,6 +2,11 @@ A [tuple] (named in [named_perspective], unnamed in [unnamed_perspective]) of [constants] that make a [query] true, i.e., substituting the [free_variables] of the [query] by these constants yields a [query] which evaluates to true +- [counting_query_answers] +- [factorized_representation] +- [tuple_testing] +- [query_enumeration] + Up: [query] Aliases: query answers diff --git a/query_boolean b/query_boolean @@ -11,6 +11,8 @@ In [logic], this is called a [sentence] - [Boolean_UCQ] - [Boolean_CRPQ] +[computational_problem]: [query_evaluation_Boolean] + Up: [query] Aliases: boolean query diff --git a/query_compilation b/query_compilation @@ -0,0 +1,7 @@ +# Query compilation + +computing a representation from a [knowledge_compilation_class] on the [provenance] of a query + +see [provenance_circuit] + +Up: [knowledge_compilation] diff --git a/query_evaluation b/query_evaluation @@ -21,6 +21,8 @@ - [query_evaluation_constraints] - [query_evaluation_constraint_satisfaction] +- [query_evaluation_boolean] + Up: [database_theory_problem] -See also: [query_language], [enumeration_query_answers], [homomorphism_problem] +See also: [query_language], [enumeration_query_answers], [homomorphism_problem], [provenance_circuit] diff --git a/query_recursive b/query_recursive @@ -1,12 +1,13 @@ # Query recursive - [regular_path_query] +- [CRPQ] - [datalog] - with [negation] - with [aggregation] Up: [query_language] -Aliases: recursive query, recursive queries +Aliases: recursive query, recursive queries, query recursion -See also: [query_nonrecursive] +See also: [query_nonrecursive], [CFL_reachability] diff --git a/query_relevance b/query_relevance @@ -0,0 +1,7 @@ +# Query relevance + +Given a [database] D, a [Boolean_query] Q, and a [fact] f of D, we say that f is *relevant* to Q on D if f belongs to a [minimal_match] of Q in D + +See [bienvenu2026how] + +Up: [provenance] diff --git a/query_resilience b/query_resilience @@ -1,4 +1,4 @@ -# Resilience +# Query resilience The *resilience* of a [query] Q on a [database] D is the minimal number of [tuples] to be deleted from D so that Q is not satisfied: - can be 0 if Q is false on D diff --git a/reachability b/reachability @@ -8,4 +8,4 @@ Up: [computational_problem], [graph_theory] -Aliases: reachability problem, reachability problems +Aliases: reachability problem, reachability problems, graph reachability diff --git a/regular_language_dichotomies b/regular_language_dichotomies @@ -1,16 +0,0 @@ -# Regular language dichotomies - -- [aaronson2019quantum] about [quantum_query_complexity] -- [amarilli2021dynamic] about [dynamic_membership] -- [bathie2025trichotomy] about [property_testing_formal_languages] - -- [ganardi2024regular] on [space_complexity] in [sliding_window] model - -- [bagan2020trichotomy] about [simple_path_trichotomy] -- [martens2023trichotomy] about [trail_trichotomy] - -- [amarilli2026out] about [out_of_order_membership] - -Up: [regular_language], [dichotomy] - -See also: [trichotomy], [query_stratification] diff --git a/rematch b/rematch @@ -1,10 +0,0 @@ -# Rematch - -- https://rematchcl.web.app/ / rematch.cl -- https://github.com/REmatchChile/REmatch-paper -- [riveros2023rematch] -- [bossonney2024demonstrating] - -notion of [earliest_answering] according to [bossonney2024demonstrating] - -Up: [enumeration_spanner] diff --git a/repair_notions b/repair_notions @@ -3,6 +3,7 @@ - [subset_repair] - [optimal_subset_repair], a [subset_repair] that [optimizes] a cost - can also do [insertions] of [tuples] in some cases +- [minimal_repairs] Up: [database_repairs] diff --git a/reversible_circuits b/reversible_circuits @@ -0,0 +1,11 @@ +# Reversible circuits + +A [circuit] where the gates are taken from a family of functions that do [permutations] of the [Boolean_valuations] + +See, e.g., [saeedi2013synthesis] + +Up: [circuit_classes] + +Aliases: circuit reversible, reversible circuit + +See also: [quantum_computing] diff --git a/rpq_query_evaluation b/rpq_query_evaluation @@ -13,6 +13,8 @@ survey: [barcelo2013querying] - [rpq_counting_answers] - [rpq_output_sensitive] +Generalization: [CFL_reachability] + Up: [regular_path_query], [query_evaluation] Aliases: RPQ evaluation diff --git a/satisfiability_weighted_ddnnf_negation b/satisfiability_weighted_ddnnf_negation @@ -1,10 +1,19 @@ # Satisfiability weighted ddnnf negation -The [computational_problem] of deciding whether a [dDNNF] has a [falsifying_assigment] of a given weight? +The [computational_problem] of deciding whether a [dDNNF] has a [falsifying_assigment] of at least a given weight +- weight is given as a weight on each literal +- up to renormalization, up to negation + - 0 has weight 0 + - 1 has positive weight -Already challenging for [orthogonal_DNF], cf [satisfiability_weighted_orthogonal_DNF_negation] +In the absence of weight this is [satisfiability_dnnnf_negation] which can be done thanks to [counting] + +It is tractable when weights are written in [unary], by [dynamic programming]: we know how many assignments there are of each weight, and how many satisfying assignments there are on each weight -But tractable when weights are written in [unary] +We can do [satisfiability_weighted_ddnnf] of deciding whether there is an assignment of at least this weight, by storing the maximum weight +- of course exact weight is [NP_hard] by reduction from [subset_sum] + +Already challenging for [orthogonal_DNF], cf [satisfiability_weighted_orthogonal_DNF_negation] Related to [ddnnf_complementation] diff --git a/sdnnf b/sdnnf @@ -6,4 +6,4 @@ like [DNNFs] but [structured] Up: [knowledge_compilation_classes], [dnnf], [structuredness] -Aliases: SDNNFs +Aliases: SDNNFs, structured DNNF, structured DNNFs diff --git a/sequence b/sequence @@ -4,12 +4,17 @@ - [Kleene_sequence] - [De_Bruijn_sequence] -- [arithmetic_progression] - [hailstone_sequence] - [Recamans_sequence] +- [linear_recurrence_sequence] + - [arithmetic_progression] ## Concepts - [subsequence] +## Open problems + +- [skolem_problem] + Up: [mathematics] diff --git a/sharp_dnnf b/sharp_dnnf @@ -1,6 +1,9 @@ -# Sharp dnnf +# Sharp DNNF -admits an [FPRAS] according to [meel2024fpras] -- generalization (uses their result) in [hecher2025alternation] +It is [sharpP_hard] + +[sharp_dnnf_approximation] Up: [sharp_sat] for [dnnf] + +Aliases: sharpDNNF diff --git a/sharp_dnnf_approximation b/sharp_dnnf_approximation @@ -0,0 +1,8 @@ +# Sharp dnnf approximation + +The #DNNF problem admits an [FPRAS] according to [meel2024fpras] +- generalization (uses their result) in [hecher2025alternation] + +Up: [sharp_dnnf], [fpras] + +Aliases: sharp DNNF approximate, sharpDNNF approximate, sharpDNNF approximation diff --git a/sharp_nfa b/sharp_nfa @@ -9,9 +9,13 @@ [computational_complexity]: - [sharpp]-hard - by reduction from [sharp_satisfiability_dnf] + - cf [angeliki2017complete] slide 34 + - cf [irwin2022complexity] - [spanl]-complete - admits a [fpras]: [arenas2021nfa] Up: [sharp_automaton], [automata_nondeterministic] See also: [sharp_dfa], [sharp_cfg] + +Aliases: sharpNFA diff --git a/shortest_path b/shortest_path @@ -12,6 +12,7 @@ Types: Related: - [shortest_path_practice] +- [shortest_path_DAG] Variants: - [shortest_path_almost] diff --git a/shortest_path_dag b/shortest_path_dag @@ -0,0 +1,5 @@ +# Shortest path DAG + +The *shortest path DAG* for a [graph] G and [vertices] s and t is the [DAG] of the [vertices] and [edges] that can occur in a [shortest_path] between s and t (assuming positive [edge_weights]) + +Up: [shortest_path] diff --git a/shuffle b/shuffle @@ -6,9 +6,12 @@ A [word] w is a *shuffle* of two [words] u and v if we can interleave the charac - [shuffle_membership] - a finite set of [words] can be decomposed into at most one multiset of which it is the shuffle: - see [berstel2002shuffle] +- [shuffle_product_problem] [shuffle] of [CFGs], cf [barloy2026shuffles] Up: [formal_language_operator] Aliases: interleaving + +See also: [perfect_shuffle] diff --git a/skolem_problem b/skolem_problem @@ -0,0 +1,13 @@ +# Skolem problem + +https://en.wikipedia.org/wiki/Skolem_problem + +The [computational_problem] of [deciding] whether a [linear_recurrence_sequence] takes the value 0 + +[NP_hard], see [blondel2002deciding] + +Up: [sequence] + +See also: [skolem_mahler_lech_theorem] + +Aliases: Skolem's problem, Pisot problem, Pisot's problem diff --git a/smallest_antichain b/smallest_antichain @@ -0,0 +1,7 @@ +# Smallest antichain + +Question: in the [boolean_lattice], what is the smallest cardinality of an [antichain] that spans an [ideal] having a certain [cardinality]? + +studied in [sunilchandrad2026smallest] + +Up: [antichain] diff --git a/smallest_witness b/smallest_witness @@ -9,6 +9,9 @@ easy for [full_CQs], so hardness comes from [projection] - [miao2019explaining], with [ptime] algorithm for a specific tuple - [hu2023finding], [best_paper_award] at [icdt_2024] +- [minimum_witness_homomorphism_closed] +- [minimum_witness_vertex_induced_subinstance] + Up: [database_theory] See also: [query_resilience], [smallest_synthetic_witness], [synthetic_witness] diff --git a/square_language b/square_language @@ -6,4 +6,4 @@ It is not a [CFL], by immediate application of the [CFL_pumping_lemma] Up: [square_word] -See also: [square_free_word_language], [square_factor_language] +See also: [square_free_word_language], [square_factor_language], [formal_language_square] diff --git a/st_reachability b/st_reachability @@ -0,0 +1,16 @@ +# st-reachability + +Given a [graph] and two [vertices] s and t, decide if there is a [path] from s to t + +[survey]: [widgerson1992complexity] + +- [st_reachability_undirected] +- [st_reachability_directed] +- [st_reachability_provenance] +- [st_reachability_dynamic] + +Up: [dynamic_graph] + +See also: [network_reliability], [st_shortest_path], [st_reliability] + +Aliases: st-connectivity diff --git a/st_reachability_directed b/st_reachability_directed @@ -0,0 +1,11 @@ +# Directed st-reachability + +Given a [directed_graph] and two [vertices] s and t, decide if there is a [directed_path] from s to t + +[NL_complete] + +Up: [st_reachability] on [directed_graphs] + +Aliases: Directed st-reachability, st connectivity directed, directed st connectivity + +See also: [undirected_st-reachability] diff --git a/st_reachability_undirected b/st_reachability_undirected @@ -5,6 +5,8 @@ Given an [undirected_graph] and two [vertices] s and t, decide if there is an [u [Complete] for [SL], and shown in [L] by [reingold2008undirected]; but open if [L] = [RL] -Up: [st_reachability] +Up: [st_reachability] on [undirected_graphs] -Aliases: undirected st-reachability, undirected reachability +Aliases: undirected st-reachability, undirected reachability, undirected st reachability, undirected st connectedness, undirected st connectivity + +See also: [directed_st-reachability] diff --git a/st_reliability b/st_reliability @@ -2,7 +2,9 @@ The case of [network_reliability] with a fixed source and target -Can be posed on [directed_graphs] and [undirected_graphs] +Can be posed: +- on [directed_graphs]: [st_reliability_directed] +- on [undirected_graphs]: [st_reliability_undirected] - [st_reliability_approximation] - [st_reliability_provenance] diff --git a/structuredness b/structuredness @@ -11,4 +11,4 @@ A [Boolean_circuit] in [DNNF] that has a [vtree] Up: [circuit_condition] -Aliases: structured circuit, structured, structured circuits, circuit structuredness +Aliases: structured circuit, structured, structured circuits, circuit structuredness, structured decomposability diff --git a/subword_closure b/subword_closure @@ -6,4 +6,4 @@ By definition it is a [subword_closed_language] Up: [subword] -See also: [subsequence_closure] +See also: [subsequence_closure], [automata_subword_closed] diff --git a/t_odd_orientation b/t_odd_orientation @@ -2,6 +2,6 @@ Given an [undirected_graph] G and subset T of vertices, a *T-odd orientation* is a [graph_orientation] of G where precisely the vertices of T have odd [in_degree] -discussed in [gravier2025note] in connection to [acyclic_orientation] +discussed in [gravier2025note] in connection to [acyclic_orientation], also in [gravier2026some] Up: [graph_orientation] diff --git a/text_algorithms b/text_algorithms @@ -0,0 +1,8 @@ +# Text algorithms + +- [pattern_matching] +- [burrows_wheeler_transform] + +Up: [stringology], [algorithms] + +Aliases: string algorithms, text algorithm, string algorithm diff --git a/threshold b/threshold @@ -3,5 +3,6 @@ - [positive_threshold_function] - [pqe_threshold] - [locally_threshold_testable_language] +- [phase_transition] in [random_graphs] Up: [mathematics] diff --git a/todas_theorem b/todas_theorem @@ -2,6 +2,8 @@ https://en.wikipedia.org/wiki/Toda%27s_theorem -The [polynomial_hierarchy] is included in [P_PP] ([P] to the [PP]) +The [polynomial_hierarchy] is included in [P_PP] ([P] with a [PP] [oracle]) + +This implies that the [polynomial_hierarchy] is included in [P_sharpP] ([P] with a [sharpP] [oracle]) Up: [theorem] diff --git a/tree_automaton b/tree_automaton @@ -9,6 +9,9 @@ Defines [regular_tree_language] - [tree_automaton_top_down] - [tree_automaton_deterministic] - [tree_automaton_nondeterministic] +- [tree_automaton_two_way] +- [tree_automaton_alternating] +- [tree_automaton_two_way_alternating] ## Variants diff --git a/tree_decomposition_updating b/tree_decomposition_updating @@ -4,3 +4,5 @@ - [gottlob2022incremental], sur [generalized_hypertree_decomposition] Up: [incremental_maintenance] of [tree_decomposition] + +Aliases: tree decomposition incremental maintenance diff --git a/treelike b/treelike @@ -9,3 +9,5 @@ - [treelike_modulo_homomorphic_equivalence] Up: [treewidth] + +Aliases: bounded treewidth diff --git a/twin_width b/twin_width @@ -23,6 +23,8 @@ guarantees that [first_order_model_checking_parameterized_complexity] is [fixed_ [twin_width_ordered] +[twin_width_computation] + Up: [width_measure] See also: [nowhere_dense], [merge_width] diff --git a/unique_ov b/unique_ov @@ -0,0 +1,7 @@ +# Unique OV + +studied in [ball2017average] + +Up: [orthogonal_vectors] + +See also: [unique_k_SAT] diff --git a/vtree b/vtree @@ -5,3 +5,5 @@ A [tree] on the [variables] of a [circuit], used to define [structuredness] Up: [tree], [knowledge_compilation] See also: [variable_order] + +Aliases: vtrees diff --git a/why_provenance b/why_provenance @@ -7,3 +7,5 @@ Specialization: [PosBool] - [why_provenance_computation] Up: [provenance] + +See also: [why_not_provenance] diff --git a/word_combinatorics b/word_combinatorics @@ -4,6 +4,7 @@ - [superpermutation] - [universal_word] - [de_bruijn_sequence] +- [lyndon_words] and [hall_words] Up: [combinatorics] on [words] diff --git a/zhao2024evaluating b/zhao2024evaluating @@ -6,4 +6,13 @@ - has [lower_bounds] but still over a class of programs, not over a specific program - reduction from [clique] -Up: [academic_paper] on [datalog_semiring_query_evaluation] +mentions cases: + +- [chain_datalog], cf [yannakakis1990graph] + - connected to [CFGs] / [context_free_reachability] + - [cubic] [data_complexity] + - chain rules of the form R(x,y) <- P1(x,z1) ... Pn(zn-1,y) + +Up: [academic_paper] on [datalog_semiring_query_evaluation], [datalog_fine_grained] + +See also: [zhao2024evaluatingb]