Hello,
first I just want to say, thanks for creating Spot, it is immensely
useful! And I think that I might have found a bug (or two).
My inputs are classic state-based NBAs. I rely on Spot to compare and
verify my determinized automata, i.e. I compare the automaton that my
tool produces with the one I get from Spot using autfilt -D -S -p (to
get a deterministic parity automaton). I use autfilt --equivalent-to=...
for the equivalence test.
Yesterday I noticed something strange. When I compare the original NBA
and my DPA, it reports that they are equivalent. Same for the original
NBA and the DPA I get from Spot. But when I compare my automaton with
the one from Spot, it says that the languages are different! So the
first thought was - something must be broken in the equivalence test.
Apparently, at least one of the three answers I got is wrong. So I used
a little Python script using the Spot API to get a word where two of the
automata do not agree on. Let's call the original NBA A, my DPA B and
the one from Spot C.
There were no words found in A׬B, ¬A×B, A׬C, ¬A×C and also B׬C.
But there IS a word in ¬B×C.
I used this word with autfilt --accept-word=... to check A, B and C. And
it turned out that in fact A and B do not accept the word, but C does,
i.e. C is incorrect.
So, to conclude, there seems to be a bug in the determinization and the
problem is not detected by the equivalence test between A and C.
I don't know about Spot internals, but if the equivalence test is using
the same determinization procedure to complement A for the required
products, then the bug in the equivalence test is a consequence of the
problem in the determinization (i.e., the equiv. test compares the wrong
DPA with basically itself), so the issues might be related.
It might be useful to know that I found the problem using Spot 2.4.4 and
it is still present in the current version 2.5.1. I also attach the
smallest automata A, B and C that illustrate the issue and the script I
used to search for the counterexample.
You can check that:
cat aut_a.hoa | autfilt --accept-word='cycle{!p;p}' -c returns 0
and
autfilt -D -S -p aut_a.hoa | autfilt --accept-word='cycle{!p;p}' -c
returns 1.
I hope this helps.
Thanks and best regards,
Anton Pirogov
