Closed eliotwrobson closed 1 year ago
@eliotwrobson I just merged the shuffle PR, so you can resume development on this one. Just switch it from Draft to Open when you're ready for me to have a look at it.
@caleb531 should be good to go now. Found a bug earlier where the counters were being called too eagerly and the numbers were going higher than needed. So I added the helper function in the utils file that handles all that logic when a counter is provided.
This actually raises the question of whether it's worth it to rename states in the NFA operations, but those don't really have huge implications for efficiency. Because the DFA minify
function has to make copies of state names, keeping the complexity of the state names down when that function is called is actually pretty important.
@eliotwrobson
This actually raises the question of whether it's worth it to rename states in the NFA operations, but those don't really have huge implications for efficiency. Because the DFA minify function has to make copies of state names, keeping the complexity of the state names down when that function is called is actually pretty important.
I'm not sure I fully understand this point. Are you suggesting we strip out the retain_names
logic of the various operation methods and just pick one of the two behaviors as the only behavior?
@caleb531 Oh no, I just meant that it might be worth adding retain_names
logic to NFA operations, but that it's not as big of a deal since the NFA operations aren't as sensitive to performance issues.
@eliotwrobson Well, I suppose that could make sense from a consistency standpoint, since DFA operations already support a retain_names
parameter. However, if we want to go to the full mile, we would really need a NFA.minify()
method (and associated per-operation minify
parameters) as well.
@caleb531 unfortunately there are no known efficient algorithms for the NFA minimization problem (see here). My comment was really just an observation, I think things are fine as-is.
EDIT: Also I think that there's very few practical applications for a minimal NFA. Having a minimal DFA is useful because it is a very space/time efficient representation of a given set, but with a minimal NFA, even checking whether a string is accepted can be an expensive operation.
@eliotwrobson Gotcha. Well, this PR looks good to me! Merging now.
Add retain names functionality to cross product. Resolves an inconsistency with expected behavior and should improve efficiency of minify function.
EDIT: Don't merge yet, just found a really dumb subtle bug in here. This also needs to wait until the shuffle product PR is merged, since that issue is present there as well (not a breaking bug).