commit e51375350c75ce33a10d42e7704c084f153174ac parent 19bd9bda48879b06f3702b9bc06209e0742bb3fd Author: Antoine Amarilli <a3nm@a3nm.net> Date: Thu, 16 Apr 2026 10:02:34 +0200 Merge remote-tracking branch 'origin/master' Diffstat:
43 files changed, 163 insertions(+), 26 deletions(-)
diff --git a/2cnf b/2cnf @@ -6,4 +6,6 @@ A [conjunctive_normal_form] [boolean_formula] where every [clause] contains two - generalization: [kcnf] - special case: [monotone2cnf] +Compilation to [OBDDs], cf [decolnet2026compilability] + Up: [conjunctive_normal_form] diff --git a/academic_paper_list b/academic_paper_list @@ -17,3 +17,5 @@ - [tziavelis2022any] Up: [list_wiki] of [academic_paper] + +See also: [interesting_papers] diff --git a/bag_semantics b/bag_semantics @@ -1,7 +1,7 @@ # Bag semantics -when [query] returns results with multiset of occurrences +The [query_semantics] where [queries] result results with [duplicates], i.e., a [multiset] -Up: [database_theory] +Up: [query_semantics] -See also: [set_semantics], [containment_bag_semantics], [multiset] +See also: [set_semantics], [containment_bag_semantics], [multiset], [bag] diff --git a/boolean_function b/boolean_function @@ -16,6 +16,9 @@ Notions: - [boolean_valuation] - [satisfying_valuation] - [falsifying_valuation] +- [decision_tree] + - [instance_complexity] + - [decision_tree_complexity] Representations: diff --git a/circuit_value_problem b/circuit_value_problem @@ -1,7 +1,11 @@ # Circuit value problem +https://en.wikipedia.org/wiki/Circuit_value_problem + Given a [Boolean_circuit] with Boolean values on the gates, and a [gate], decide if that [gate] evaluates to [true] +It is [P_complete] + Up: [decision_problem] on [circuit] -See also: [formula_value_problem] +See also: [formula_value_problem], [circuit_satisfiability_problem] diff --git a/computational_problem b/computational_problem @@ -43,4 +43,4 @@ Up: [theoretical_computer_science] -Aliases: computational problems +Aliases: computational problems, computation problem diff --git a/context_free_grammar_equivalence b/context_free_grammar_equivalence @@ -4,6 +4,8 @@ Two [CFGs] are *equivalent* if they recognize the same [formal_language] - [computational_problem]: [context_free_grammar_equivalence_problem] +in [practice]: [context_free_grammar_equivalence_practice] + Up: [context_free_grammar], [language_equivalence] Aliases: CFG equivalence, CFG equivalent, equivalent CFG, grammar equivalent diff --git a/context_free_grammar_equivalence_practice b/context_free_grammar_equivalence_practice @@ -0,0 +1,5 @@ +# Context free grammar equivalence practice + +in connection with [iltis]: [schmellenkamp2026detecting] + +Up: [context_free_grammar_equivalence], [practice] diff --git a/crossing_number b/crossing_number @@ -8,6 +8,8 @@ An [undirected_graph] is a [planar_graph] iff the crossing number is zero [crossing_number_inequality] +[crossing_number_computation] + The crossing number of [complete_bipartite_graphs] is an [open_problem], cf https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_brick_factory_problem Up: [planar_graph] diff --git a/crossing_number_computation b/crossing_number_computation @@ -0,0 +1,7 @@ +# Crossing number computation + +The [computational_problem] of computing the [crossing_number] + +It is [NP_hard], even on [simple_graphs] of bounded [pathwidth], cf [hlineny2026crossing] + +Up: [computational_problem], [crossing_number] diff --git a/database_theory b/database_theory @@ -9,6 +9,8 @@ - [query_language] - [graph_query_languages] +- [query_semantics] + See also: [databases], [database_startups], [description_logics], [finite_model_theory] Up: [research_fundamental] of [database_research] diff --git a/decision_tree b/decision_tree @@ -2,9 +2,10 @@ A way to represent a [Boolean_function] -Generalization: [bdd] +Generalization: [BDD] -The [boolean_function_equivalence] problem on decision trees can be solved in [quadratic] time, cf [cockett1987discrete] and [zantema1998equivalence] +- [decision_tree_equivalence] +- [decision_tree_complexity] Up: [knowledge_compilation_formalisms] diff --git a/decision_tree_equivalence b/decision_tree_equivalence @@ -0,0 +1,5 @@ +# Decision tree equivalence + +The [boolean_function_equivalence] problem on decision trees can be solved in [quadratic] time, cf [cockett1987discrete] and [zantema1998equivalence] + +Up: [decision_tree], [equivalence_problem] diff --git a/dsdnnf b/dsdnnf @@ -1,11 +1,13 @@ # d-SDNNF -[structuredness] [deterministic] [decomposable] [circuit] +[structured_circuit] [deterministic] [decomposable] [circuit] not closed under [complementation], cf [vinallsmeeth2024structured] by [harry] - [dSDNNF_lower_bounds] +Restriction: [TDDs], cf [capelli2026canonical] + Up: [knowledge_compilation_classes], [ddnnf], [sdnnf] Aliases: dSDNNFs, d_SDNNFs, d_SDNNF diff --git a/enumeration_tasks b/enumeration_tasks @@ -23,5 +23,6 @@ - [enumeration_topological_sort] - https://cstheory.stackexchange.com/questions/36334/enumerating-topological-sorts-of-a-vertex-labeled-dag - [enumeration_valuations] +- [enumeration_posets] Up: [enumeration] diff --git a/formula_value_problem b/formula_value_problem @@ -0,0 +1,9 @@ +# Formula value problem + +Given a [Boolean_formula] with Boolean values for the variables, decide if it evaluates to [true] + +It is [NC1_complete] + +See also: [circuit_value_problem], [tree_evaluation_problem], [formula_satisfiability_problem] + +Up: [decision_problem], [boolean_formula] diff --git a/graph_drawing b/graph_drawing @@ -0,0 +1,10 @@ +# Graph drawing + +- [rectilinear_embedding] on a [grid] + - only for [graphs] with [maximal_degree] 4 + - can be done with area O(|V|^2) + +- [straight_line_embedding] on a [grid] + - can be done in the n-2 by n-2 grid, cf [schnyder1990embedding] + +Up: [graph_embedding] diff --git a/graph_embedding b/graph_embedding @@ -4,6 +4,7 @@ - [topological_minor] - [subgraph] - [induced_subgraph] +- [graph_drawing] Up: [graph] diff --git a/guarded_second_order_logic b/guarded_second_order_logic @@ -0,0 +1,11 @@ +# Guarded second order logic + +A variant of [second_order_logic] where quantification is semantically restricted to only apply to [guarded_tuples] + +See [gradel2002back] + +Up: [monadic_second_order_logic] + +Aliases: GSO + +See also: [MSO2] diff --git a/instance_complexity b/instance_complexity @@ -0,0 +1,9 @@ +# Instance complexity + +studied in [liu2026instance] for [Boolean_functions] + +Relates to the [certificate_complexity] and [decision_tree_complexity] + +Up: [boolean_function] + +See also: [instance_optimal] diff --git a/join b/join @@ -6,6 +6,7 @@ - [self_join] - [optimal_joins] - [inequality_join] +- [join_algorithm] Up: [databases] diff --git a/monadic_second_order_logic b/monadic_second_order_logic @@ -11,6 +11,7 @@ Extensions: - [counting_monadic_second_order_logic] - [weighted_MSO] +- [guarded_second_order_logic] [Computational_complexity]: diff --git a/monadic_second_order_logic_2 b/monadic_second_order_logic_2 @@ -1,11 +0,0 @@ -# Monadic second order logic 2 - -also called "incidence encoding", corresponds to the [incidence_graph] between [vertices] and [edges] - -Can express that a [graph] has a [Hamiltonian_cycle], [max_cut], [edge_dominating_set], [graph_coloring] - -Up: [monadic_second_order_logic] - -Aliases: MSO2 - -See also: [MSO1] diff --git a/nogami2026hardness b/nogami2026hardness @@ -0,0 +1,9 @@ +# nogami2026hardness + +shows [lower_bounds] on +- [regular_expression_squaring] +- [regular_expression_backreferences] +- [regular_expression_intersection] +- [regular_expression_complement] + +Up: [academic_paper], [regular_expression_extensions_matching] diff --git a/pattern_matching b/pattern_matching @@ -27,7 +27,7 @@ - [two_way_string_matching] - [regular_expression] -- [pattern_with_variables] +- [matching_pattern_with_variables], [pattern_with_variables] - [pattern_matching_wildcards] when allowing [wildcards] - [pattern_matching_dontcare] when allowing [dontcares] (one single symbol can be anything) - [pattern_matching_compressed] on [compressed_data] diff --git a/primitive_root b/primitive_root @@ -4,6 +4,8 @@ Given a [word] v, returns the shortest [word] u such that v = u^k for some k Note that u is then a [primitive_word] +[primitive_root_computing] + Up: [operation] on [words] Aliases: primitive roots diff --git a/primitive_root_computing b/primitive_root_computing @@ -0,0 +1,9 @@ +# Primitive root computation + +The problem of [computing] the [primitive_root] of a [word] + +Can be done in [linear_time] by [pattern_matching], cf [garwychowski2010finding] for instance + +Up: [computation_problem], [primitive_root] + +Aliases: primitive root computation, computing primitive root diff --git a/provenance_reasoning b/provenance_reasoning @@ -2,6 +2,6 @@ With [description_logics]: - [ceylan2022explanations] -- [bourgaux2023semiring] +- [bourgaux2023semiring] and [bourgaux2026semiring] Up: [provenance] for [reasoning] diff --git a/query_semantics b/query_semantics @@ -0,0 +1,8 @@ +# Query semantics + +- [set_semantics] +- [bag_semantics] + +Up: [database_theory] + +See also: [named_perspective], [unnamed_perspective] diff --git a/regex b/regex @@ -10,3 +10,5 @@ can be translated to [FCreg] if there is no variable under [kleene_star] [regex_deterministic] Up: [regular_expression] + +Aliases: regular spanner, regular spanners diff --git a/regular_expression b/regular_expression @@ -9,6 +9,10 @@ Notions: - [star_height] - [generalized_star_height] +Generalization: + +- [variable_regular_expression] + [computational_problems]: - [regular_expression_matching] diff --git a/regular_expression_extensions b/regular_expression_extensions @@ -11,5 +11,11 @@ - regular expression with memory, in [graph_databases] - [regular_expression_repetition] - "bounded repetition" aka counting "x{n,m}" +- [regular_expression_squaring] +- [regular_expression_backreferences] +- [regular_expression_intersection] +- [regular_expression_complement] + +[regular_expression_matching] for extensions: [regular_expression_extensions_matching] Up: [regular_expression] diff --git a/regular_expression_extensions_matching b/regular_expression_extensions_matching @@ -0,0 +1,7 @@ +# Regular expression extensions matching + +cf [nogami2026hardness] + +Up: [regular_expression_extensions], [regular_expression_matching] + +Aliases: regular expression matching extensions diff --git a/regular_expression_repetition_intersection_nonemptiness b/regular_expression_repetition_intersection_nonemptiness @@ -3,3 +3,5 @@ it is [PSPACE_complete], cf https://cstheory.stackexchange.com/a/57014 Up: [regular_expression_repetition], [Intersection_nonemptiness] + +See also: [regular_expression_intersection] diff --git a/regular_expression_squaring b/regular_expression_squaring @@ -6,6 +6,6 @@ makes [language_inclusion] and [language_universality] [EXPSPACE_complete], cf [ but [intersection_nonemptiness] still in [PSPACE], like for [regular_expression_repetition], cf [regular_expression_repetition_intersection_nonemptiness] -Up: [regular_expression], [squaring] +Up: [regular_expression_extensions], [squaring] See also: [regular_expression_repetition] diff --git a/shuffle b/shuffle @@ -7,6 +7,8 @@ A [word] w is a *shuffle* of two [words] u and v if we can interleave the charac - a finite set of [words] can be decomposed into at most one multiset of which it is the shuffle: - see [berstel2002shuffle] +[shuffle] of [CFGs], cf [barloy2026shuffles] + Up: [formal_language_operator] Aliases: interleaving diff --git a/simple_graph b/simple_graph @@ -7,3 +7,5 @@ A [graph] which is not a [multigraph], i.e., there cannot be multiple copies of Up: [graph] See also: [set_semantics] + +Aliases: simple graphs diff --git a/spanner b/spanner @@ -54,6 +54,6 @@ Up: [formal_language_theory], [database_theory] -See also: [graph_spanner], [capture_variable], [annotation_automata] +See also: [graph_spanner], [capture_variable], [annotation_automata], [variable_regular_expression] Aliases: document spanner, document spanners, spanners diff --git a/spanner_regular b/spanner_regular @@ -6,3 +6,5 @@ two equivalent definitions ([peterfreund2019complexityb] section 2.4): - optionally with [difference] Up: [spanner] + +See also: [variable_regular_expression] diff --git a/structuredness b/structuredness @@ -4,6 +4,9 @@ A [Boolean_circuit] in [DNNF] that has a [vtree] - [circuit_restructuring] +[Circuit_classes]: +- [dSDNNFs] + Up: [circuit_condition] Aliases: structured circuit, structured, structured circuits, circuit structuredness diff --git a/tree_decomposition b/tree_decomposition @@ -5,6 +5,7 @@ - [balancing_tree_decomposition] - [tree_decomposition_linked] - [tree_decomposition_normalized] +- [tree_decomposition_spread] See also: [treewidth], [core_tentacle] diff --git a/tree_decomposition_spread b/tree_decomposition_spread @@ -0,0 +1,11 @@ +# Tree decomposition spread + +The *spread* of a [vertex] in a [tree_decomposition] is the number of [bags] in which it occurs + +See https://cstheory.stackexchange.com/a/57070 + +Up: [tree_decomposition] + +Aliases: spread + +See also: [degree], [variable_occurrences] diff --git a/tree_evaluation_problem b/tree_evaluation_problem @@ -2,7 +2,7 @@ You have a [tree] and you want to evaluate a [bottom_up_nondeterministic_tree_automaton] on the tree, in a [nonuniform] sense where each [node] is labeled by the transition function -Covers in particular the evaluation of [Boolean_formulas] and the acceptance of a fixed [tree_automaton] +Covers in particular the [formula_value_problem] and the acceptance of a fixed [tree_automaton] Sometimes considered specifically on [complete_binary_trees] and on functions at the nodes given as input. @@ -12,5 +12,3 @@ It is in O(log n log log n), cf [cook2023tree] and [goldreich2024cook] Up: [computational_problem] on [tree] Aliases: TreeEval, tree evaluation - -See also: [formula_value_problem]