Permanent problem IDPPL 142
Formal languages
Improve Robson’s O(n²⁄⁵(log n)³⁄⁵) upper bound on the number of DFA states needed in the worst case to separate two distinct length-n words.
Improve Robson’s O(n²⁄⁵(log n)³⁄⁵) upper bound on the number of DFA states needed in the worst case to separate two distinct length-n words.
Personal cash offer stated in Shallit’s official talk. The live talks page records subsequent updates, including a paid solution to one omitted problem; confirm claim procedure with the sponsor before relying on the award.