wiki_research

commit 835e18f3c96940afa0036e0e7507a94917391117
parent 79a9161f059e7495e99bc3333443ca411b73b302
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue,  8 Jul 2025 12:23:59 +0200

Merge branch 'master' of a3nm.net:git/wiki_research

Diffstat:
3sat
 | 
2
++
automatic_relation
 | 
2
++
crpq
 | 
2
++
graph_colorability
 | 
2
++
homomorphism
 | 
1
+
homomorphism_problem
 | 
8
++++++++
query_evaluation
 | 
2
+-
regular_query
 | 
2
++
simple_regular_expressions
 | 
4
++++
simple_transitive_expressions
 | 
2
+-

10 files changed, 25 insertions(+), 2 deletions(-)
diff --git a/3sat b/3sat
@@ -9,3 +9,5 @@ It is [np_complete]
 Up: [sat_variants]
 
 See also: [2sat], [schaefers_dichotomy_theorem]
+
+Aliases: 3 SAT
diff --git a/automatic_relation b/automatic_relation
@@ -6,6 +6,8 @@ symbol, i.e., [automaton_synchronous]
 - Paper about this: [barcelo2023separating]
 - [automatic_relation_algebra]
 
+Example: the [infinite_binary_tree] is an automatic relation
+
 Special case: [recognizable_relations]
 
 Generalization: [deterministic_rational_relations], [rational_relations]
diff --git a/crpq b/crpq
@@ -9,6 +9,8 @@
 - [C2RPQ]
 - [UCRPQ]
 - [conjunctive_context_free_path_query]
+- [regular_query]
+  - [regular_query_with_memory]
 
 [Computational_problems]:
 - [CRPQ_containment]
diff --git a/graph_colorability b/graph_colorability
@@ -6,3 +6,5 @@ The [computational_problem] of, given a [graph] G and number k, deciding whether
 - [3_colorability]
 
 Up: [computational_problem], [graph_coloring]
+
+Aliases: k colorability
diff --git a/homomorphism b/homomorphism
@@ -4,6 +4,7 @@
 - [homomorphism_equivalence]
 - [graph_homomorphism]
 - [homomorphism_count]
+- [homomorphism_problem]
 
 Variants: [homomorphism_variants]
 
diff --git a/homomorphism_problem b/homomorphism_problem
@@ -0,0 +1,8 @@
+# Homomorphism problem
+
+The [decision_problem], given two [relational_structures] G and H, of deciding whether there is a [homomorphism] from G to H
+
+This is in [NP], and [NP_hard] even if H is a fixed graph
+- e.g., can code [k_colorability]
+
+Up: [decision_problem], [homomorphism]
diff --git a/query_evaluation b/query_evaluation
@@ -21,4 +21,4 @@
 
 Up: [database_theory_problem]
 
-See also: [query_language], [enumeration_query_answers]
+See also: [query_language], [enumeration_query_answers], [homomorphism_problem]
diff --git a/regular_query b/regular_query
@@ -12,3 +12,5 @@ Generalizations:
 Studied in [reutter2017regular]
 
 Up: [query_language]
+
+Aliases: regular queries
diff --git a/simple_regular_expressions b/simple_regular_expressions
@@ -1,5 +1,7 @@
 # Simple regular expressions
 
+- notion of [STEs] from [martens2018evaluation]
+
 - version defined in [figueira2024boundedness]
   - allows w^* for a [word] w
   - allows [regular_expressions] without [Kleene_star]
@@ -20,3 +22,5 @@ Conjunctive Regular Path Queries"
   - otherwise [query_containment] drops to [Pi_p_2] or [PSPACE]
 
 Up: [regular_expression]
+
+Aliases: SRE
diff --git a/simple_transitive_expressions b/simple_transitive_expressions
@@ -6,4 +6,4 @@ Introduced in [martens2018evaluation]
 
 Up: [regular_expression]
 
-Aliases: simple transitive expression, STE
+Aliases: simple transitive expression, STE, STEs