commit 5539ed5fbc18933a8ada7f4b4a37b0129dae05c6
parent cdbad1f6851cbbe5435cea270d5f0a51da16fbd3
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 19 Aug 2025 21:23:57 +0200
commit with codex
Diffstat:
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
