Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add/remove for DAFSAs #1

Open
larsmans opened this issue Feb 22, 2013 · 1 comment
Open

Add/remove for DAFSAs #1

larsmans opened this issue Feb 22, 2013 · 1 comment

Comments

@larsmans
Copy link

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:

(I've been toying with these things myself lately, but didn't come round to publishing any code.)

@danieldk
Copy link
Owner

Thanks! I think I have seen that paper before. I might add a mutable variant at some point, but the representation in the final automaton (which uses several arrays of primitives, since Java doesn't allow you to use unboxed classes) may not be that great/efficient for mutation.

My first goals is to have some work-alike for Guava's immutable collections where the key (or key and value) is a String.

Of course, patches are welcome :).

danieldk added a commit that referenced this issue Mar 23, 2013
As suggested in #1.

Todo: optimize reachability checking, the current implementation is *slow*.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants