Combinatorics and Discrete Probability Seminar
Zachary Chase
UC San Diego
Separating words
Abstract: We show that for any distinct n-bit strings x and y, there is a deterministic finite automaton on n^{1/3} states that accepts x but not y. The methods involve complex analysis and elementary number theory.
Monday March 10, 2025 at 3:00 PM in 1227 SEO