commit 068e347fa40af89b51a92c3e97505efc76552992
parent 665a287bc34a84a61bea18b19f87429ccf88cff6
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sat, 21 Jun 2025 22:38:28 +0200
commit with codex
Diffstat:
8 files changed, 76 insertions(+), 0 deletions(-)
diff --git a/c_d_hypergraph b/c_d_hypergraph
@@ -0,0 +1,8 @@
+# (c,d)-hypergraph
+
+[Hypergraph] where there is a bound on the [cardinality] of the [intersection] of any c [hyperedges]
+- cf [lanzinger2023fpt]
+
+See also: [edge_intersection_size]
+
+Up: [hypergraph]
diff --git a/carmeli2023conjunctive b/carmeli2023conjunctive
@@ -0,0 +1,7 @@
+# Carmeli2023conjunctive
+
+[academic_paper] by [luc_segoufin] and [nofar] about [enumeration_self_joins]
+
+Up: [academic_paper] about [enumeration_self_joins]
+
+See also: [tagging_trick]
diff --git a/chen2010constraint b/chen2010constraint
@@ -0,0 +1,7 @@
+# Chen2010constraint
+
+[academic_paper] by [hubie_chen] and [martin_grohe]
+
+About [constraint_satisfaction_problem] when the input is concisely represented as [gdnf]
+
+Up: [academic_paper], [constraint_satisfaction_problem_knowledge_compilation]
diff --git a/edge_intersection_size b/edge_intersection_size
@@ -0,0 +1,7 @@
+# Edge intersection size
+
+In a [hypergraph], the maximal cardinality of the intersection of two [hyperedges]
+
+Generalization [c_d_hypergraph]
+
+Up: [hypergraph]
diff --git a/hamiltonian_cycle_multiple b/hamiltonian_cycle_multiple
@@ -0,0 +1,8 @@
+# Hamiltonian cycle multiple
+
+A generalization of [Hamiltonian_cycle] where you can go over each [vertex] at most k times for some k.
+- By https://courses.engr.illinois.edu/cs374/fa2016/homework/hw10.pdf this problem is also [NP_complete].
+- A [star] with large [degree] is an example of a [graph] having no such generalized [hamiltonian_path] for any k
+- mentioned here https://cstheory.stackexchange.com/questions/53492/name-for-a-cyclic-path-in-a-graph-that-visits-every-vertex-while-minimizing-the
+
+Up: [hamiltonian_cycle]
diff --git a/indexed_grammar_unambiguity b/indexed_grammar_unambiguity
@@ -0,0 +1,6 @@
+# Indexed grammar unambiguity
+
+https://cstheory.stackexchange.com/questions/51895/is-there-any-inherently-ambiguous-indexed-language/52184#52184
+- open if there are [indexed_languages] that are [inherently_ambiguous]
+
+Up: [indexed_grammar], [unambiguity]
diff --git a/lutz2022complete b/lutz2022complete
@@ -0,0 +1,16 @@
+# lutz2022complete
+
+[academic_paper] by [carsten] and [leif]
+
+Complexity [trichotomy] for [ontology_mediated_query] about [el] class:
+
+We know that every [OMQ] from (EL,AQ) (or (EL,CQ)) falls into one of the following classes:
+
+- [AC0] / [FO-rewritable]
+- [NL]
+ - but there is actually an infinite hierarchy here: every [OMQ] that can be evaluated in NL translates into an equivalent [linear_datalog] program, and for every [datalog_width] k of such a program ([arity] of [IDB_relations]) we find an [OMQ] that actually needs width at least k in the rewriting (equivalently: has [pathwidth] k)
+- [PTime]
+
+[Open_question]: extend to [ELI]
+
+Up: [academic_paper]
diff --git a/weights b/weights
@@ -0,0 +1,17 @@
+# Weights
+
+- [weighted_mso]
+ - [counting_weighted_mso]
+
+- [graph_weighted]
+ - [connectivity_weighted]
+
+- [hamming_weight]
+
+- [weighted_median]
+
+- [spanner_weighted]
+- [automata_weighted]
+- [weighted_language]
+
+Up: [theoretical_computer_science]
