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

Add counterexample to the output of NFA language equivalence and inclusion tests #439

Open
ondrik opened this issue Sep 26, 2024 · 2 comments

Comments

@ondrik
Copy link
Member

ondrik commented Sep 26, 2024

bool are_equivalent(const Nfa& lhs, const Nfa& rhs, const Alphabet* alphabet,

It is often necessary to obtain a counterexample to equivalence/inclusion. If the equivalence does not hold, we would like to know what is a word in the symmetric difference of the two automata and in the language of which automaton it is.

@Adda0 Adda0 removed their assignment Sep 26, 2024
@jurajsic
Copy link
Member

jurajsic commented Oct 8, 2024

For inclusion you can call

bool is_included_antichains(const Nfa& smaller, const Nfa& bigger, const Alphabet* alphabet = nullptr, Run* cex = nullptr);

or
bool is_included_naive(const Nfa& smaller, const Nfa& bigger, const Alphabet* alphabet = nullptr, Run* cex = nullptr);

directly to get counterexample.
We should add it to dispatcher functions too.

However, it seems that at least for is_included_antichains, the counterexample is incorrect right now (#440).

@jurajsic
Copy link
Member

jurajsic commented Oct 8, 2024

Also, related #113

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

3 participants