commit fafe2f80ff2cafa6d534f172c970a76ddbb828bf
parent 009fa19fe09f16c17e34aaf26ed4e9e9b9438398
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 14 Apr 2026 09:36:19 +0200
commit with codex
Diffstat:
15 files changed, 69 insertions(+), 4 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/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/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/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/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/join b/join
@@ -6,6 +6,7 @@
- [self_join]
- [optimal_joins]
- [inequality_join]
+- [join_algorithm]
Up: [databases]
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/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/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/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]
