Just to let you know, there's a variant of Daciuk et al.'s algorithm that supports adding a string to an DFA, retaining minimality: - [Incremental Construction and Maintenance of Minimal Finite-State Automata](http://acl.ldc.upenn.edu/J/J02/J02-2004.pdf) (I've been toying with these things myself lately, but didn't come round to publishing any code.)