wiki_research

commit ea22af887fb004d8325be11810aad6e125f38ec5
parent eb8967737074f80d77d02d0e42006c49df84048d
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Wed, 20 Aug 2025 12:04:14 +0200

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

Diffstat:
regular_path_query
 | 
2
++
rpq_counting_answers
 | 
2
+-
rpq_semantics
 | 
10
++++++++++
rpq_simple_paths
 | 
13
+++++++++++++
simple_path_rpq_problem
 | 
2
+-
trail
 | 
2
++

6 files changed, 29 insertions(+), 2 deletions(-)
diff --git a/regular_path_query b/regular_path_query
@@ -2,6 +2,8 @@
 
 [query] on [graph_database] defined by [regular_expression]
 
+[RPQ_semantics]
+
 ## Extensions
 
 - [2rpq]
diff --git a/rpq_counting_answers b/rpq_counting_answers
@@ -5,4 +5,4 @@
 
 Up: [counting_query_answers], [RPQ]
 
-See also: [rpq_query_evaluation]
+See also: [rpq_query_evaluation], [RPQ_counting_paths]
diff --git a/rpq_semantics b/rpq_semantics
@@ -0,0 +1,10 @@
+# RPQ semantics
+
+The semantics of [RPQs] can be:
+
+- [simple_paths]: [RPQ_simple_paths]
+- [trails]: [regular_trail_query]
+- [walks] (can have unbounded length)
+- [shortest_paths]
+
+Up: [regular_path_query]
diff --git a/rpq_simple_paths b/rpq_simple_paths
@@ -0,0 +1,13 @@
+# RPQ simple paths
+
+[RPQs] evaluated in [simple_paths] semantics; common in [RPQ_practice], but can cause intractability
+
+For instance:
+- [bagan2020trichotomy]
+- [simple_path_trichotomy]
+- [simple_path_rpq_enumeration]
+- [rpq_counting_simple_paths]
+
+Up: [rpq_semantics], [RPQ], [simple_paths]
+
+Aliases: RPQ simple path
diff --git a/simple_path_rpq_problem b/simple_path_rpq_problem
@@ -1,6 +1,6 @@
 # Simple path rpq problem
 
-Decide if there is a [simple_path] satisfing a [RPQ] from a vertex s to a vertex t in a [graph]
+Decide if there is an [RPQ_simple_path] match from a vertex s to a vertex t in a [graph]
 
 Topic of the [simple_path_trichotomy]
 
diff --git a/trail b/trail
@@ -5,3 +5,5 @@ A [walk] where [vertices] can repeat, but not [edges]
 Up: [path]
 
 See also: [walk], [simple_path]
+
+Aliases: trails