commit c2d1c851372dbaea576feb1dd95235db2cc9b2dd
parent 33811b492e68d0fd3e636820a65d57548a2e4f12
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 30 May 2025 12:22:54 +0200
commit with codex
Diffstat:
13 files changed, 55 insertions(+), 16 deletions(-)
diff --git a/2rpq b/2rpq
@@ -7,3 +7,5 @@ Generalization: [C2RPQs]
Up: [graph_query_languages], [regular_path_query]
Aliases: 2RPQs
+
+See also: [two_way_regular_expressions]
diff --git a/conjunctive_query_boolean b/conjunctive_query_boolean
@@ -4,4 +4,4 @@
Up: [conjunctive_query], [query_boolean]
-Aliases: Boolean CQ, Boolean CQs, Boolean conjunctive query
+Aliases: Boolean CQ, Boolean CQs, Boolean conjunctive query, BCQ, BCQs
diff --git a/cut_rank b/cut_rank
@@ -0,0 +1,11 @@
+# Cut rank
+
+The [cut_rank] of a subset of vertices U in a [graph] with vertex set V is the [rank] of the [adjacency_matrix] between U and the complement V\U
+
+Defined in [bojanczyk2024rank]
+
+Bounding the cutrank amounts to bounding the [matrix_diversity] of the [adjacency_matrix], cf [bojanczyk2025low] Lemma 2.1
+
+See also: [rankwidth]
+
+Up: [graph_theory]
diff --git a/diversity b/diversity
@@ -0,0 +1,11 @@
+# Diversity
+
+a measure of how "diverse" a set is
+
+- [enumeration_diversity]
+- [conjunctive_query_diversity]
+- [matrix_diversity]
+
+Up: [measure]
+
+See also: [representativity]
diff --git a/graph_sparse b/graph_sparse
@@ -4,6 +4,8 @@ https://en.wikipedia.org/wiki/Dense_graph
An [undirected_graph] where the number of [edges] is o(n^2), for n the number of [vertices]
+- [weakly_sparse]
+
Up: [graph_family]
Aliases: sparse graph, sparse graphs
diff --git a/guarded_fragment b/guarded_fragment
@@ -1,14 +0,0 @@
-# Guarded fragment
-
-- [gf2]
-- [gc2]: like [fo2] with [counting_quantifiers]
-- [gck]
-- [guarded_TGD]
-
-According to [cate2023craig], enjoys [finite_model_property] but not [craig_interpolation]
-
-[Online_workshop]: [GF25]
-
-See also: [michael], [finite_model_theory], [guarded_negation], [pratt_hartmann], [frontier_guarded], [guard_atom]
-
-Up: [logic]
diff --git a/matrix_diversity b/matrix_diversity
@@ -0,0 +1,7 @@
+# Matrix diversity
+
+The number of different rows of a [matrix] plus the number of different columns of a [matrix]
+
+cf [bojanczyk2025low], with connections to [rank]
+
+Up: [diversity], [matrix]
diff --git a/semiring_provenance b/semiring_provenance
@@ -9,3 +9,5 @@ For [query_optimization], you need the [semiring] to be [semiring_commutative]
Up: [provenance], [semirings]
See also: [provenance_polynomial]
+
+Aliases: provenance semiring, provenance semirings
diff --git a/string_squaring b/string_squaring
@@ -0,0 +1,5 @@
+# String squaring
+
+the [string_transformation] a_1 ... a_n => (a_1 ... a_n)^n
+
+Up: [string_transformation]
diff --git a/ubcq b/ubcq
@@ -0,0 +1,5 @@
+# UBCQ
+
+[disjunction] of [Boolean_CQs]
+
+Up: [UCQ], [BCQ]
diff --git a/union b/union
@@ -3,6 +3,7 @@
- [union_trick]
- [disjoint_union]
- [language_union]
-- [query_union]
Up: [set_theory], [boolean_operator]
+
+See also: [disjunction]
diff --git a/weakly_sparse b/weakly_sparse
@@ -0,0 +1,5 @@
+# Weakly sparse
+
+A [graph_family] is *weakly sparse* if there is an integer t such that every graph G from the family does not contain the [biclique] K_{t,t} as a [subgraph]
+
+Up: [sparse_graphs]
diff --git a/width_measure_linear b/width_measure_linear
@@ -2,5 +2,7 @@
- [pathwidth]
- [lmim_width]
+- [linear_rankwidth]
+- [cutwidth]
Up: [width_measure]
