wiki_research

commit c47a098d433c93c8f640ba2ddc673bc09bb68d32
parent f1aeda9f646f94c66d9641491cde9426dad17285
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue, 26 May 2026 17:27:56 +0200

commit with codex

Diffstat:
automata_alternating
 | 
2
++
automata_problems
 | 
1
+
automaton_primality
 | 
7
+++++++
boolean_function_classes
 | 
1
+
courcelle_theorem
 | 
2
++
formal_language_theory
 | 
1
+
graph_labeling
 | 
1
+
repair_notions
 | 
1
+

8 files changed, 16 insertions(+), 0 deletions(-)
diff --git a/automata_alternating b/automata_alternating
@@ -6,6 +6,8 @@ Generalizes [NFAs]
 
 Can be seen as an [arena] in [game_theory]
 
+- [automata_alternating_provenance]
+
 Up: [automata_types]
 
 Aliases: alternating automaton, alternating automata
diff --git a/automata_problems b/automata_problems
@@ -8,6 +8,7 @@ On one [automaton]:
 - [automaton_cofiniteness]
 - [synchronizing_word_problem]
 - [counter_freeness_testing]
+- [automaton_primality]
 
 On two [automata]:
 
diff --git a/automaton_primality b/automaton_primality
@@ -0,0 +1,7 @@
+# Automaton primality
+
+decide if an input DFA can be written as the [automaton_intersection] of input DFAs that all have strictly less states
+
+it in [NP_hard] to decide, see [spenner2026deciding]
+
+Up: [automata_problems]
diff --git a/boolean_function_classes b/boolean_function_classes
@@ -4,6 +4,7 @@
 - [positive_threshold_function]
 - [boolean_function_regular]
 - [boolean_function_evasive]
+- [boolean_function_unate]
 
 Up: [boolean_function]
 
diff --git a/courcelle_theorem b/courcelle_theorem
@@ -8,6 +8,8 @@ Also: bounded [cliquewidth] if we are given a witness of cliquewidth
 
 time f(|phi|, width) times linear in the graph
 
+[courcelle_logspace]
+
 Up: [theorem] on [monadic_second_order_logic_model_checking], [algorithmic_metatheorem]
 
 Aliases: Courcelle's theorem
diff --git a/formal_language_theory b/formal_language_theory
@@ -55,6 +55,7 @@ Studies [formal_languages]
 - [interchange_lemma] https://en.wikipedia.org/wiki/Interchange_lemma
   - other such results: https://cstheory.stackexchange.com/a/54032
 - [myhill_nerode_theorem]
+- [factorization_forest]
 
 Up: [theoretical_computer_science]
 
diff --git a/graph_labeling b/graph_labeling
@@ -4,6 +4,7 @@
 - [distance_labeling]: cf [gawrychowski2023better]
 - [graceful_labeling]
 - [canonical_labeling]
+- [adjacency_labeling]
 
 Up: [graph]
 
diff --git a/repair_notions b/repair_notions
@@ -3,6 +3,7 @@
 - [subset_repair]
 - [optimal_subset_repair], a [subset_repair] that [optimizes] a cost
 - can also do [insertions] of [tuples] in some cases
+- [minimal_repairs]
 
 Up: [database_repairs]