wiki_research

commit 5a60570de8f78f7465a629eeb20668d9680f8487
parent d47d04dc69b5b70d520b7d1e4cf281fbc90127f2
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Thu, 30 Oct 2025 18:39:40 +0100

Merge remote-tracking branch 'origin/master'

Diffstat:
automaton_emptiness
 | 
2
+-
automaton_intersection
 | 
3
++-
intersection
 | 
2
++
matrix_multiplication_algorithms
 | 
1
+

4 files changed, 6 insertions(+), 2 deletions(-)
diff --git a/automaton_emptiness b/automaton_emptiness
@@ -4,4 +4,4 @@ It is [nl_complete] to check [automaton] emptiness
 
 Up: [automata_problems], [language_emptiness]
 
-See also: [automaton_finiteness], [universality_automata]
+See also: [automaton_finiteness], [universality_automata], [intersection_nonemptiness]
diff --git a/automaton_intersection b/automaton_intersection
@@ -2,8 +2,9 @@
 
 can be done with [product_construction]
 
-[computational_complexity] bounds on [automaton_emptiness] of intersection of constant number of [DFAs]: [oliveira2018intersection]
+[computational_complexity] bounds on [automaton_emptiness] of intersection of constant number of [DFAs] (especially on [intersection_nonemptiness]): [oliveira2018intersection] and [oliveira2020fine]
 - connections to [3SUM] and [triangle_detection]
+- also [ascone2025are] on [regular_expressions] (for [intersection_nonemptiness])
 
 Up: [automaton_constructions], [intersection]
 
diff --git a/intersection b/intersection
@@ -8,3 +8,5 @@
 Up: [boolean_operator]
 
 Aliases: intersections, cap
+
+See also: [intersection_nonemptiness]
diff --git a/matrix_multiplication_algorithms b/matrix_multiplication_algorithms
@@ -2,5 +2,6 @@
 
 - [strassens_algorithm]
 - [karatsuba_algorithm]
+- Multiplication of [Boolean_matrices] (with [AND] and [OR]) in expected quadratic time in [oneil1973fast]
 
 Up: [algorithms] for [matrix_multiplication]