commit 208ed427e4ca46955da5f45dd65fe28a4dd630a5 parent 254a640c188fa2e48d54d49b125ea354a451f3d9 Author: Antoine Amarilli <a3nm@a3nm.net> Date: Thu, 26 Jun 2025 15:34:21 +0200 commit with codex Diffstat:
47 files changed, 292 insertions(+), 40 deletions(-)
diff --git a/aut_rec_separability b/aut_rec_separability @@ -0,0 +1,5 @@ +# Aut rec separability + +The [formal_language_separation] problem of [automatic_relations] by [recognizable_relations], studied in [morvan2025homomorphism] Chapter VIII + +Up: [formal_language_separation], [automatic_relations], [recognizable_relations] diff --git a/bienstock1991quickly b/bienstock1991quickly @@ -0,0 +1,5 @@ +# bienstock1991quickly + +They show that for every [forest] F with n vertices, a graph with [pathwidth] at least n-1 has a [minor] which is [graph_isomorphic] to F + +Up: [academic_paper], [obstruction_treewidth_pathwidth] diff --git a/boolean_formula b/boolean_formula @@ -14,4 +14,4 @@ Up: [representation] of [boolean_function] See also: [boolean_circuit], [knowledge_compilation_classes] -Aliases: formula boolean +Aliases: formula boolean, Boolean formulae, Boolean formulas diff --git a/boolean_formula_read_polarity_once b/boolean_formula_read_polarity_once @@ -0,0 +1,9 @@ +# Read-polarity-once Boolean formula + +A [Boolean_formula] is *read once* if every [literal] occurs at most once + +cf [callegaro2013read] + +Up: [boolean_formula_read_once] + +Aliases: Read polarity once Boolean formula diff --git a/bounded_problem b/bounded_problem @@ -1,5 +1,7 @@ # Bounded problem +"Bounded problems" are decidable versions of potentially undecidable problems. For instance, "bounded universality" means "given k, check universality for words of length up to k" + studied in [axelsson2008analyzing] - [language_inclusion_bounded] @@ -9,3 +11,5 @@ studied in [axelsson2008analyzing] - [CFG_ambiguity_bounded] Up: [formal_language_computational_problem] + +Aliases: bounded problems diff --git a/cd_membership_problem b/cd_membership_problem @@ -5,6 +5,9 @@ Terminology from [morvan2025homomorphism]: for C and D two classes of inputs wit - input: an object in C - output: does the object belong to D? +Special cases: +- [rec_membership_problem] + Up: [computational_problem] See also: [Formal_language_separation] diff --git a/core b/core @@ -18,6 +18,6 @@ The [core] of an [instance] A is a [subinstance] B of A such that there is no [h Up: [homomorphism] -See also: [chase_core], [CQ_minimization] +See also: [chase_core], [CQ_minimization], [rigid] Aliases: cores diff --git a/elimination_forest b/elimination_forest @@ -0,0 +1,7 @@ +# Elimination forest + +An *elimination forest* F for a graph G is a [forest] whose [nodes] are labeled injectively with vertices of G, with the requirement that for every [edge] (u,v) of G the nodes of F labeled by u and v are comparable, i.e., one is an [ancestor] of the other + +It can be defined on [hypergraphs] and [relational_structures] via the [Gaifman_graph] + +Up: [treedepth] diff --git a/finite_regular_colorability_automatic_graphs b/finite_regular_colorability_automatic_graphs @@ -0,0 +1,7 @@ +# Finite regular colorability automatic graphs + +Given an [automatic_presentation] of an [automatic_graph] G, does there exist a finite number k of [regular_languages] L_1, ..., L_k that partition Sigma^* such that they form a [k_coloring] of G? + +When we fix k to any constant, this problem is [undecidable], cf [morvan2025homomorphism] + +Up: [computational_problem], [automatic_graph] diff --git a/formal_language_computational_problems b/formal_language_computational_problems @@ -3,12 +3,13 @@ - [membership_problem] - [language_inclusion] - [language_equivalence] -- [bounded_problem] - [finiteness_problem] - [emptiness_testing] - [cofiniteness_testing] - [cd_membership_problem] +- [bounded_problems] + Up: [formal_language] Aliases: formal language computational problem diff --git a/formal_language_separation b/formal_language_separation @@ -1,5 +1,6 @@ # Formal language separation +[Computational_problem] parameterized by [formal_language_classes] C and C': 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 @@ -8,6 +9,10 @@ a [formal_language] L in class C' separates them if L1 subseteq L and L cap L2 i generalization to multiple languages: [formal_language_covering] - cf [place2018covering] +Cases: +- [rat_rec_separability] +- [aut_rec_separability] + See also: [barcelo2023separating] Up: [formal_language_theory] diff --git a/function b/function @@ -25,6 +25,11 @@ Basic notions: - [function_partial] - [function_image] - [function_preimage] +- [function_inverse] +- [involution] +- [function_idempotent] +- [function_composition] +- [currying] Up: [mathematics] diff --git a/function_idempotent b/function_idempotent @@ -0,0 +1,7 @@ +# Function idempotent + +A [function] such that f circ f = f + +Up: [function], [idempotence] + +See also: [idempotent_element], [idempotent_power], [involution] diff --git a/graph_coloring b/graph_coloring @@ -41,4 +41,4 @@ Up: [graph_problem] See also: [chromatic_number], [graph_colorability] -Aliases: graph colored +Aliases: graph colored, k coloring diff --git a/graph_family b/graph_family @@ -6,6 +6,7 @@ A (generally [infinite]) set of [graphs] - [triangle] - [hole] - [path] +- [tournament] - [tree] - [polytree] - [multitree] diff --git a/graph_minor b/graph_minor @@ -1,13 +0,0 @@ -# Graph minor - -- [edge_contraction] - -[graph_minor_testing] - -- [graph_immersion] - -Up: [graph_embedding] - -See also: [robertson_seymour], [topological_minor], [excluded_minor], [forbidden_minor], [induced_minor], [minor_closed] - -Aliases: graph minors, minor, minors diff --git a/grid_minor b/grid_minor @@ -11,6 +11,6 @@ used for [hardness] results, e.g., [grohe2007complexity] Up: [theorem] about [grid_graph] -See also: [grid_minor_directed] +See also: [grid_minor_directed], [treewidth] Aliases: grid minor extraction, grid extraction diff --git a/height b/height @@ -1,7 +1,12 @@ # Height -A [tree] consisting of only a singleton [root] node has height 0; otherwise the height is 1 plus the [maximum] of the [height] of the [rooted_subtrees] that are [children] of the [root] +The *height* of a [tree] and of a [forest] is defined inductively: +- The height of a [singleton_tree] consisting of only a singleton [root] node is zero +- The height of a [tree] is otherwise one plus the height of the [forest] of the [children] of the [root] +- The height of a [forest] is the [maximum] of the heights of the [trees] of the [forest] Up: [parameter] on [tree] See also: [depth] + +Aliases: tree height, forest height diff --git a/homomorphism b/homomorphism @@ -11,4 +11,4 @@ Up: [mathematics] See also: [core], [retraction_minimum_violation] -Aliases: homomorphisms +Aliases: homomorphisms, hom diff --git a/involution b/involution @@ -0,0 +1,9 @@ +# Involution + +https://en.wikipedia.org/wiki/Involution_(mathematics) + +A [function] which is its own [function_inverse] + +Up: [function] + +See also: [Function_idempotent] diff --git a/maximal_degree b/maximal_degree @@ -0,0 +1,12 @@ +# Maximal degree + +The [maximum] of the [degree] of [vertices] in a given [graph] + +Special cases: +- A [degree_0_graph] is an [empty_graph] +- A [degree_1_graph] is a [disjoint_union] of [isolated_edges] +- A [degree_2_graph] is a [disjoint_union] of [path_graphs] and [cycle_graphs] +- A [degree_3_graph] is a [graph] where the maximum degree is 3 + - see also [cubic_graph], where the degree of each vertex is 3 + +Up: [degree], [maximum] diff --git a/mindnf b/mindnf @@ -0,0 +1,7 @@ +# MinDNF + +The [minimization_truth_table] problem for [DNFs] + +It is [NP_complete], cf [allender2008minimizing] + +Up: [minimization_truth_table] diff --git a/minimization_truth_table b/minimization_truth_table @@ -0,0 +1,11 @@ +# Minimization truth table + +The [minimization] [computational_problem] for [Boolean_functions] given as an explicit [truth_table]: + +- [MinDNF] for [DNFs] +- [MFSP] for [Boolean_formulas] +- [MCSP] for [Boolean_circuits] + +Up: [minimization], [Boolean_function] + +See also: [Minimum_equivalent_problem] diff --git a/minimum b/minimum @@ -7,6 +7,6 @@ The smallest element of an [order] Up: [mathematics_basic_concepts] -See also: [maximum], [minimization] +See also: [maximum], [minimization], [minimal] Aliases: min diff --git a/minimum_circuit_size_problem b/minimum_circuit_size_problem @@ -6,6 +6,8 @@ Clearly in [nptime] and not known to be [np_hard], cf [ilango2022minimum] [minimum_circuit_size_problem_arithmetic_circuit] -See also: [minimum_formula_size_problem], [addition_chain] +See also: [minimum_formula_size_problem], [addition_chain], [Minimum_equivalent_circuit] -Up: [minimization] of [boolean_circuit] +Up: [minimization_truth_table] of [boolean_circuit] + +Aliases: MCSP diff --git a/minimum_equivalent_circuit b/minimum_equivalent_circuit @@ -0,0 +1,9 @@ +# Minimum equivalent circuit + +The [minimum_equivalent_problem] for [Boolean_circuits] + +Mentioned in [umans2001minimum], it is [coNP_hard] + +Up: [minimum_equivalent_problem], [Boolean_circuit] + +See also: [MCSP] diff --git a/minimum_equivalent_dnf b/minimum_equivalent_dnf @@ -4,6 +4,10 @@ Given a [DNF] φ and integer k, does there exist a [DNF] which is [equivalent] t Studied in [umans2001minimum], showed to be [Sigma_P_2_complete] -See also: [umans2001minimum], [Minimum_formula_size_problem], [DNF_minimization], [goldsmith2008complexity] +Generalization to arbitrary [Boolean_formulas] (and also to bounded-depth [Boolean_formulas] with other depth bounds): [MEE] -Up: [computational_problem] +Related problem via [truth_tables] on [Boolean_formulas] ([Minimum_formula_size_problem]) and [Boolean_circuits] ([MCSP]) + +See also: [umans2001minimum], [DNF_minimization], [goldsmith2008complexity] + +Up: [minimum_equivalent_problem], [DNF] diff --git a/minimum_equivalent_expression b/minimum_equivalent_expression @@ -0,0 +1,11 @@ +# Minimum equivalent expression + +Given a [Boolean_formula] φ (over the [de_Morgan_basis]) and an integer s, decide if there is a [Boolean_formula] (over the same basis) with size at most s which represents the same [Boolean_function] + +[Sigma_P_2_complete] by [buchfuhrer2011complexity] + +Up: [minimum_equivalent_problem], [Boolean_formula] + +See also: [Minimum_equivalent_DNF], [MCSP] + +Aliases: MEE diff --git a/minimum_equivalent_problem b/minimum_equivalent_problem @@ -0,0 +1,11 @@ +# Minimum equivalent problem + +The [minimization] [computational_problem], given a [Boolean_function] in a certain representation, of finding an equivalent representation of minimum size + +- [minimum_equivalent_DNF] for [DNFs] +- [minimum_equivalent_expression] for [Boolean_formulas] +- [minimum_equivalent_circuit] for [Boolean_circuits] + +Up: [minimization] + +See also: [Minimization_truth_table] diff --git a/minimum_formula_size_problem b/minimum_formula_size_problem @@ -0,0 +1,13 @@ +# Minimum formula size problem (MFSP) + +Given the explicit [truth_table] of a [Boolean_function], and a positive integer s, determine if there is an equivalent [Boolean_formula] (over the [de_Morgan_basis], i.e., with [AND] and [OR] and [NOT] gates) with at most s leaves + +Not in [PTIME] under [exponential_time_hypothesis], cf [ilango2022minimum] + +Notion of a [search_to_decision_reduction] + +See also: [minimum_circuit_size_problem], [umans2001minimum], [minimum_equivalent_DNF], [Minimum_equivalent_expression] + +Up: [minimization] of [formula_boolean] + +Aliases: MFSP diff --git a/obstruction b/obstruction @@ -0,0 +1,16 @@ +# Obstruction + +From [morvan2025homomorphism]: an *obstruction* of a finite structure B is a finite structure D that does not have a [homomorphism] to B + +Whenever an obstruction D of B has a [homomorphism] to a structure A, then it witnesses that A does not have a homomorphism to B + +Via [homomorphism_duality], this is a [query_match] of the dual of B + +[obstruction_critical] + +Variant: [obstruction_set] for [minors] +- [obstruction_treewidth_pathwidth] + +Up: [graph] + +Aliases: obstructions diff --git a/obstruction_critical b/obstruction_critical @@ -0,0 +1,15 @@ +# Critical obstruction + +A *critical obstruction* is an obstruction such that any [strict_substructure] is not an obstruction + +Terminology from [larose2007characterisation] + +The set of critical obstructions is a [homomorphism_dual] + +If there are infinitely many critical obstructions, then the structure does not admit [finite_duality] + +Example: the [zigzag_graphs] form an infinite set of critical obstructions for the [2_path] + +Up: [obstruction] + +Aliases: critical obstruction, critical obstructions diff --git a/obstruction_set b/obstruction_set @@ -0,0 +1,6 @@ +# Obstruction set + +From [chlebikova2002structure]: given a [minor_closed] [graph_class] H, the +*obstruction set* is the set of [graphs] in the [complement] of H that are [minimal] for the [minor_order] + +Up: [obstruction_treewidth_pathwidth] diff --git a/parity_p b/parity_p @@ -8,4 +8,4 @@ https://en.wikipedia.org/wiki/Parity_P Up: [parity], [complexity_class] -See also: [parity_fine_grained], [Z_2Z] +See also: [parity_fine_grained], [Z_2Z], [parity_L] diff --git a/path_graph b/path_graph @@ -0,0 +1,22 @@ +# Path graph + +[graph] consisting of a [path] + +- [one_way_path] +- [two_way_path] + +generalisations of the "path" graph class: + +- [path_excentricity] + - [graph_caterpillar] + - [graph_lobster] + +special case: + +- 1-path is a single [edge] +- [2_path] +- [3_path] + +Up: [graph] + +See also: [path] diff --git a/pathwidth b/pathwidth @@ -8,6 +8,8 @@ like [treewidth] but for [tree_decomposition] which is a [path] - [path_decomposition] +- [pathwidth_obstruction] + Up: [width_measure], [path] -See also: [treewidth], [path_excentricity], [obstruction], [treelength] +See also: [treewidth], [path_excentricity], [treelength] diff --git a/primal_graph b/primal_graph @@ -1,11 +1,21 @@ # Primal graph -[graph_undirected]: +An [undirected_graph] defined from a [DNF] or from a [hypergraph] or from a [relational_structure]. + +For a [DNF]: - vertices are variables - edge connects two variables if they co-occur in a clause -if [clause_width] is unbounded then contains large [clique] +If the [clause_width] of a [DNF] is unbounded then the primal graph contains arbitrarily large [cliques] + +For a [hypergraph]: +- vertices are vertices +- edge connects two variables if they co-occur in a [hyperedge] + +Likewise for [relational_structures] Up: [graph_undirected] for [conjunctive_normal_form] See also: [dual_graph], [incidence_graph], [primal_treewidth] + +Aliases: Gaifman graph diff --git a/query b/query @@ -15,4 +15,4 @@ Up: [database_theory] Aliases: queries -See also: [knowledge_compilation_query] +See also: [knowledge_compilation_query], [query_match] diff --git a/rat_rec_separability b/rat_rec_separability @@ -0,0 +1,5 @@ +# Rat rec separability + +The [formal_language_separation] problem of [rational_relations] by [recognizable_relations], studied in [morvan2025homomorphism] Chapter VIII + +Up: [formal_language_separation], [rational_relations], [recognizable_relations] diff --git a/rational_relation b/rational_relation @@ -6,6 +6,8 @@ Special cases: - [rational_relation_deterministic] - [automatic_relation] +[rec_membership_problem] + Up: [word_relation] Aliases: rational relations diff --git a/rec_membership_problem b/rec_membership_problem @@ -0,0 +1,10 @@ +# Rec membership problem + +The [cd_membership_problem] asking, given a [rational_relation], whether it is [relation_equivalent] to a [recognizable_relation] + +[morvan2025homomorphism] p233: +- The problem is [undecidable] in general +- But [decidable] given a [deterministic_rational_relation] +- It is [PSPACE_complete] given an [automatic_relation] + +Up: [cd_membership_problem], [rational_relation], [recognizable_relation] diff --git a/rigid b/rigid @@ -0,0 +1,9 @@ +# Rigid + +A [structure] is *rigid* if its only [automorphism] is the identity + +Up: [structure] + +See also: [core] + +Aliases: rigid structure diff --git a/rst_query b/rst_query @@ -6,4 +6,4 @@ The prototypical [SJFCQ] for which [PQE] is [sharpP_hard]: Up: [pqe_ucq] -See also: [Hk_queries] +See also: [Hk_queries], [3_path] diff --git a/tournament b/tournament @@ -0,0 +1,10 @@ +# Tournament + +https://en.wikipedia.org/wiki/Tournament_(graph_theory) + +A [graph_directed] where every possible edge exists with one direction +- i.e., a [graph_orientation] of a [complete_graph] + +A [transitive_tournament] is the [transitive_closure] of a [path_graph] + +Up: [graph_family] diff --git a/transitive_tournament b/transitive_tournament @@ -0,0 +1,7 @@ +# Transitive tournament + +The [transitive_closure] of a [path_graph] + +Up: [tournament] + +See also: [Transitivity] diff --git a/treedepth b/treedepth @@ -0,0 +1,7 @@ +# Treedepth + +https://en.wikipedia.org/wiki/Tree-depth + +The *treedepth* of an [undirected_graph] G is the minimum [forest_height] of an [elimination_forest] for G + +Up: [width_measure] diff --git a/turing_machine_symmetric b/turing_machine_symmetric @@ -1,9 +0,0 @@ -# Turing_machine_symmetric - -A [Turing_machine] where all transitions can be taken in reverse - -[Turing_machine_symmetric_automata] - -Up: [turing_machine] - -See also: [automata_symmetric]