wiki_research

commit 089f668f3fed9dab5f0d94c48a8d93183ffd9def
parent 78a29a663da7222b0636c5ce713665a7ec68f7e5
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Wed, 23 Jul 2025 13:05:33 +0200

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

Diffstat:
canonical_labeling
 | 
2
+-
circuit_complexity_query_evaluation
 | 
3
++-
deterministic_k_turn_pushdown_automata_equivalence
 | 
8
++++++++
deterministic_one_turn_pushdown_automata
 | 
9
+++++++++
enumeration_random_order
 | 
1
+
graph_database_practical
 | 
1
+
k_turn_pushdown_automata
 | 
7
+++++++
one_turn_pushdown_automaton
 | 
9
+++++++++

8 files changed, 38 insertions(+), 2 deletions(-)
diff --git a/canonical_labeling b/canonical_labeling
@@ -7,7 +7,7 @@ https://mathoverflow.net/a/11715
 
 also called "graph canonization"
 
-See also: [graph_isomorphism], [minimization_automaton]
+See also: [graph_isomorphism], [minimization_automaton], [complete_graph_invariant]
 
 Up: [graph]
 
diff --git a/circuit_complexity_query_evaluation b/circuit_complexity_query_evaluation
@@ -1,6 +1,7 @@
 # Circuit complexity query evaluation
 
-[wang2022query]
+- [wang2022query]
+- [fan2025circuit] for [self_joins]
 
 Up: [circuit_complexity] of [query_evaluation]
 
diff --git a/deterministic_k_turn_pushdown_automata_equivalence b/deterministic_k_turn_pushdown_automata_equivalence
@@ -0,0 +1,8 @@
+# Deterministic k turn pushdown automata equivalence
+
+- the [equivalence_problem] is [decidable], cf [valiant1974decidability]
+- subsumed by [senizergues1997equivalence]
+
+Up: [equivalence_problem], [k_turn_pushdown_automata]
+
+Aliases: deterministic k turn PDA equivalence
diff --git a/deterministic_one_turn_pushdown_automata b/deterministic_one_turn_pushdown_automata
@@ -0,0 +1,9 @@
+# Deterministic one turn pushdown automata
+
+[one_turn_pushdown_automaton] which is [automaton_deterministic]
+
+[equivalence_problem] is [decidable], cf [deterministic_k_turn_PDA_equivalence]
+
+Up: [one_turn_pushdown_automaton]
+
+Aliases: deterministic one turn PDA, deterministic one turn PDAs
diff --git a/enumeration_random_order b/enumeration_random_order
@@ -1,6 +1,7 @@
 # Enumeration in random order
 
 - [chen2023random]
+- [chen2025towards]
 
 See also: [uniform_sampling]
 
diff --git a/graph_database_practical b/graph_database_practical
@@ -3,6 +3,7 @@
 Implementations:
 
 - [Neo4j]
+- for [RPQs]: [garcia2025pathdb]
 
 Query languages:
 
diff --git a/k_turn_pushdown_automata b/k_turn_pushdown_automata
@@ -5,6 +5,13 @@ limits the alternation between [push_operation] and [pop_operation]
 - introduced in [ginsburg1966finite]
 - mentioned in [ganardi2018sliding]
 
+subclasses:
+
+- [one_turn_pushdown_automaton]
+  - [deterministic_one_turn_pushdown_automata]
+- [deterministic_k_turn_pushdown_automata]
+  - [deterministic_k_turn_pushdown_automata_equivalence]
+
 Up: [pushdown_automaton]
 
 See also: [visibly_pushdown_languages]
diff --git a/one_turn_pushdown_automaton b/one_turn_pushdown_automaton
@@ -0,0 +1,9 @@
+# One turn pushdown automaton
+
+[k_turn_pushdown_automata] with k=1
+
+- [deterministic_one_turn_pushdown_automata]
+
+Up: [k_turn_pushdown_automata]
+
+Aliases: one turn PDA