wiki_research

commit 162c64f3f62a0a8e35f9ef688e5b41f226dec54d
parent 1ebeabac60ef4dfb356022df89a6666a40ac3562
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue, 15 Sep 2026 19:39:21 +0200

commit with codex

Diffstat:
automaton_query_complexity
 | 
8
++++++++
cernys_conjecture
 | 
2
+-
counter_free_automata
 | 
2
+-
function_idempotent
 | 
2
+-
idempotence
 | 
1
+
query_complexity
 | 
2
++

6 files changed, 14 insertions(+), 3 deletions(-)
diff --git a/automaton_query_complexity b/automaton_query_complexity
@@ -0,0 +1,8 @@
+# Automaton query complexity
+
+The [query_complexity] of membership to the [formal_language] accepted by an [automaton]
+
+- [aaronson2019quantum] studies it for [quantum_complexity] and in particular talks about the fact that it is either constant or linear depending on the language
+- [automaton_query_complexity_nondeterministic]
+
+Up: [query_complexity]
diff --git a/cernys_conjecture b/cernys_conjecture
@@ -4,7 +4,7 @@ https://en.wikipedia.org/wiki/Synchronizing_word#Length
 
 It is known that an [automata] with a [synchronizing_word] may have no smaller synchronizing word than length (n-1)^2: is there a matching upper bound?
 
-See also: [completely_reachable_automata]
+See also: [completely_reachable_automata], [shortest_synchronizing_word]
 
 Up: [synchronizing_word], [open_problem]
 
diff --git a/counter_free_automata b/counter_free_automata
@@ -10,4 +10,4 @@ Up: [automata_classes]
 
 Aliases: automata counter-free, automata counter free, automaton counter free
 
-See also: [permutation_automaton]
+See also: [permutation_automaton], [idempotent_word]
diff --git a/function_idempotent b/function_idempotent
@@ -4,4 +4,4 @@ A [function] such that f circ f = f
 
 Up: [function], [idempotence]
 
-See also: [idempotent_element], [idempotent_power], [involution]
+See also: [idempotent_element], [idempotent_power], [involution], [idempotent_word]
diff --git a/idempotence b/idempotence
@@ -6,6 +6,7 @@
   - [Semiring_n_idempotent]
   - [additively_idempotent_semiring]
   - [multiplicatively_idempotent_semiring]
+- [idempotent_word]
 
 Up: [mathematics]
 
diff --git a/query_complexity b/query_complexity
@@ -6,6 +6,8 @@ Also called "expression complexity"
 
 Introduced in [vardi1982complexity]
 
+- [automaton_query_complexity]
+
 Up: [database_theory_complexity]
 
 See also: [combined_complexity], [data_complexity]