search

caleb531 / automata

A Python library for simulating finite automata, pushdown automata, and Turing machines
https://caleb531.github.io/automata/
MIT License
349 stars 64 forks source link

Simplify minify logic #133

Closed EduardoGoulart1 closed 1 year ago

EduardoGoulart1 commented 1 year ago

@caleb531 @eliotwrobson I wanted to drop a proposal to decouple the logic of the cross-product. The idea is to turn the exploration method into a function that receives an initial state and an expansion function and applies BFS using only that. This makes the current implementation cleaner and will also significantly simplify the implementation for allow_partial

I did some microbenchmarks and noted that the overhead is relatively small.

Please do not make a full review of this PR. If you approve the design I will clean it up to make it ready to merge.

coveralls commented 1 year ago

Coverage Status

Coverage: 99.956% (-0.04%) from 100.0% when pulling ffeaae47be9ad1f1224801ca30f23e1abb084b57 on EduardoGoulart1:simplify-minify-logic into b9c195a80a5aa5977c7c0b81d5a72ba56bb12551 on caleb531:main.

coveralls commented 1 year ago

Coverage Status

Coverage: 99.956% (-0.04%) from 100.0% when pulling ffeaae47be9ad1f1224801ca30f23e1abb084b57 on EduardoGoulart1:simplify-minify-logic into b9c195a80a5aa5977c7c0b81d5a72ba56bb12551 on caleb531:main.

coveralls commented 1 year ago

Coverage Status

Coverage: 99.956% (-0.04%) from 100.0% when pulling ffeaae47be9ad1f1224801ca30f23e1abb084b57 on EduardoGoulart1:simplify-minify-logic into b9c195a80a5aa5977c7c0b81d5a72ba56bb12551 on caleb531:main.

coveralls commented 1 year ago

Coverage Status

Coverage: 99.956% (-0.04%) from 100.0% when pulling ffeaae47be9ad1f1224801ca30f23e1abb084b57 on EduardoGoulart1:simplify-minify-logic into b9c195a80a5aa5977c7c0b81d5a72ba56bb12551 on caleb531:main.

EduardoGoulart1 commented 1 year ago

By using this design, support for allow_partial can be added quite naturally by adapting the state transition functions.

Also, the issubset, isdisjoint and isempty methods can be implemented faster by switching to DFS instead of BFS

eliotwrobson commented 1 year ago

This design seems cool! I think we might want to wait till an initial version of the type hints PR is merged, since this changes a significant number of those. But I think this refactor with the generator makes things more flexible.

Also, the issubset, isdisjoint and isempty methods can be implemented faster by switching to DFS instead of BFS

I don't think this is always true. Those functions are searching for a single state as a counterexample, in the worst case they all have to search every reachable state.

caleb531 commented 1 year ago

@EduardoGoulart1 I like the approach of this architecture, but also agree with @eliotwrobson about the BFS matter. Fortunately, I have just merged the types PR (#131) so you can continue to work on this PR.

EduardoGoulart1 commented 1 year ago

Sorry, I think I expressed myself badly. Yes, both have the same worst-case complexity. But I was starting from the assumption that end states are "deeper" in the DFA, which we might want to verify.

In any case, isempty will profit from early-stopping. But, I won't change anything related to it in this PR

EduardoGoulart1 commented 1 year ago

Closing this one. See https://github.com/caleb531/automata/pull/139