Bug in WMethod Oracle Implementation #26
Merged
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Problem: The WMethodOracle is not implemented correctly. It produces too few test sequences and does not find a counterexample even though its maxmimum state variable is high enough.
Please see and try the tests included in this PR.
Context: The WMethodOracle uses
combinations
fromitertools
for extending the middle of its testing set. However, these sequences are much too short to actually cover the entire state space given by the maximum state variable.I believe that the author though the second argument of
combinations
is the length of the resulting sequences, when in reality it is the number of buckets to split the alphabet into. See https://docs.python.org/3/library/itertools.html#itertools.combinationsProblem 2: Also, on an unrelated note, I saw that the calculation for the characterization set does not work for Moore Machines in general. Calling
compute_characterization_set
on the Moore Machine generated bygenerate_hypothesis
in the newly added test will result in the algorithm claiming that the machine is non-canonical, even though it isn't.