Intersecting Dense Automata: Constructions, Complexity and Certificates 20.7.2026 | IMDEA Software Institute Sunday, July 19, 2026, 11:00am 302-Mountain View and Zoom3 (https://zoom.us/j/3911012202, password:@s3). Neha Rino, PhD Researcher, University of Warwick, UK Intersecting Dense Automata: Constructions, Complexity and Certificates Abstract: Given k nondeterministic finite automata (NFA), finding an NFA that recognises the intersection of their languages is a basic problem in automata theory. We observe that the classical Cartesian product construction is non-optimal in the worst case, that is, if the automata have many transitions. For a fixed alphabet, the Cartesian product of two NFA may have Θ(m²) transitions if these NFA have at most n states and m transitions each. In this talk, we describe alternative constructions with O(mn) transitions; or O(mn^(k − 1)) for the intersection of k NFA (for fixed k ≥ 2 and alphabet Σ). This gives a faster algorithm for deciding NFA intersection emptiness, that is, deciding whether k given NFA accept a word in common. We also show that this new algorithm is optimal, unless there exists a breakthrough combinatorial algorithm for detecting (k + 1)-cliques in undirected graphs. Lastly, we show how these new product constructions allow us to certify NFA intersection emptiness faster. https://software.imdea.org/events/invited-talks/2026/07-19