wiki_research

commit f6c06ce6fe20247d53c4b4bf1bd7ddc89d170adf
parent ae1ac14578fb629a48db1d3c4f804485628fc768
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Thu, 24 Jul 2025 10:55:03 +0200

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

Diffstat:
automata_complementation
 | 
2
++
automata_types
 | 
1
+
canonical_labeling
 | 
2
+-
circuit_complexity_query_evaluation
 | 
3
++-
context_free_grammar
 | 
4
++++
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
+++++++++

11 files changed, 45 insertions(+), 2 deletions(-)
diff --git a/automata_complementation b/automata_complementation
@@ -7,3 +7,5 @@
 Up: [complementation], [automata]
 
 Aliases: automaton complement, automaton complementation
+
+See also: [automata_complementation_practice]
diff --git a/automata_types b/automata_types
@@ -30,5 +30,6 @@
 - [automata_weighted]
 - [omega_automata]
 - [automata_multitape]
+- [limited_automata]
 
 Up: [automata]
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/context_free_grammar b/context_free_grammar
@@ -44,6 +44,10 @@
 - [probabilistic_grammar]
 - [multiple_context_free_grammar]
 
+## Results
+
+- [Greibach's_theorem]
+
 See also: [regular_language], [chomsky_hierarchy], [context_free_language], [inherently_ambiguous], [graph_grammar], [semilinear_set], [language_power_series], [Hyperedge_replacement_grammar]
 
 Up: [formal_language_theory], [formal_grammar]
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