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

Formalize automaton processing #65

Closed
timbray opened this issue Jun 12, 2022 · 1 comment
Closed

Formalize automaton processing #65

timbray opened this issue Jun 12, 2022 · 1 comment

Comments

@timbray
Copy link
Owner

timbray commented Jun 12, 2022

There is quite a bit of complexity in supporting both NFAs and DFAs. This is not strictly necessary since there are well-known algorithms for converting NFAs to DFAs. This might make AddPattern more expensive, but this should be investigated and benchmarked.

Similarly, anything_but.go is complex and hard to understand. Also perhaps not necessary because there are well-known arguments for taking the complement of a DFA and for doing intersections (I think?) differences. Similarly, the AddPattern cost should be investigated.

timbray added a commit that referenced this issue Jun 23, 2022
Related to #65

Signed-off-by: Tim Bray <[email protected]>
@timbray
Copy link
Owner Author

timbray commented Jul 2, 2022

Addressed in a few commits ending in f811b97 - still work to do on AddPattern cost, will create an issue for that.

@timbray timbray closed this as completed Jul 2, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant